조합(Combination)

위 식을 재귀를 사용해 짜면,

import java.util.Scanner;

public class Main07 {
	
	int[][] temp = new int[35][35];
	//숫자가 커지면 소요 시간이 기하급수적으로 커짐
	// 이를 방지하기 위한 배열

	public int Combination(int n, int r) {

		if(temp[n][r] > 0) return temp[n][r];
		if(n==r || r==0) return 1;

		else return temp[n][r] = Combination(n-1, r-1) + Combination(n-1, r);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main07 T = new Main07();
		Scanner kb = new  Scanner(System.in);
		
		int n = kb.nextInt();
		int r = kb.nextInt();
		
		System.out.println(T.Combination(n, r));
	}

}

 

 

---

 

 

Combination + DFS 조합문제

위와같은 파스칼 삼각형의 경우 각각

3C0, 3C1, 3C2, 3C3번 곱해져서 더해진다 ⇒ (31)+(13)+(23)+(41)

즉

int[] combinationArr;
for(int i = 0; i < N; i++) { Combination(N-1, i) }

int[] ans = new int[N];

일 때, int배열 combinationArr 와 ans 의 같은 인덱스 값들을 곱한 합이 F와 같은 것이 나올 때까지 DFS를 활용해 답 ans 를 구하면 된다

import java.util.Scanner;

public class Main {

	static int n, f;
	static int[] arr, combArr, check; // 정답 배열, 정답곱 횟수배열, DFS용 체크배열
	static int[][] temp = new int[11][11]; //Combination 결과값 저장소
	boolean flag = false;
	
	public int Combination(int n, int r) {
		if(temp[n][r]>0) return temp[n][r];
		if(n==r || r==0) return 1;
		else return temp[n][r] = Combination(n-1, r-1) + Combination(n-1, r);

	}
	
	public void DFS(int L, int sum) {
		if(flag) return;
		if(L==n) {
			if(sum==f) {
				for(int x : arr) System.out.print(x + " ");
				flag = true;
			}
		}
		else{
			for(int i = 1; i <= n; i++) {
				if(check[i] == 0) {
					check[i] = 1;
					arr[L] = i;
					DFS(L+1, sum + combArr[L]*arr[L]);
					check[i] = 0;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		
		n = kb.nextInt();
		f = kb.nextInt();
		
		arr = new int[n];
		combArr = new int[n];
		check = new int[n+1];
		//답의 각 인덱스 * Combination 결과 = f
		for(int i = 0; i < n; i++) {
			combArr[i] = T.Combination(n-1, i); 
		}
		
		T.DFS(0, 0);
	}

}

 

 

---

 

 

import java.util.Scanner;

public class Main {

	static int n, m;
	
	static int[] ansArr;
	
	public void DFS(int level, int start) {
		if(level == m) {
			for(int x : ansArr) System.out.print(x + " ");
			System.out.println();
			return;
		}
		else {
			for(int i=start; i<=n; i++) {
				ansArr[level] = i;
				DFS(level+1, i+1);
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		
		n = kb.nextInt();
		m = kb.nextInt();
		
		ansArr = new int[m];
		T.DFS(0, 1);
	}

}