조합(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));
	}

}

조합 + 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 배열 조합 Arr의 곱과 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);
	}

}