수열추측 (조합)

1. 이전에 만든 조합 및 permutation을 이용하여 수열 값을 구한다.

2. N(자연수의 갯수), M 값이 주어질 때 다음과 같은 형태가 그려짐.. 

ex) 4 16

3 1 2 4

 4 3 6

  7 9

   16

3. 구체적인 풀이법 보다는 combination 및 permutation 활용에 대한 습득이 중요하겠다.

class Main {

	static int m, n;
	static boolean flag = false;
	public int DFS(int n, int r) {
		if (comb[n][r] > 0)
			return comb[n][r];

		if (r == 0 || n == r)
			return 1;
		else {
			return comb[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
		}
	}

	public void perm(int level, int sum, int[] pm, int[] ch, int[] b) {
		if( flag) return;
		if (level == n) {
			if (sum == m) {
				for (int x : pm)
					System.out.print(x + " ");
				System.out.println();
				flag =true;
			}
		} else {

			for (int i = 1; i <= n; i++) {
				if (ch[i] == 0) {
					ch[i] = 1;
					pm[level] = i;
					perm(level + 1, sum + (pm[level] * b[level]), pm, ch, b);
					ch[i] = 0;
				}
			}
		}
	}

	static int[][] comb;

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		int[] pm = new int[n];
		int[] ch = new int[n + 1];
		int[] b = new int[n+1];
		int MAX = 33 + 1;
		comb = new int[MAX][MAX];
		

		for (int i = 0; i < n; i++) {
			b[i] = M.DFS(n-1, i);
		}
//		for (int i = 0; i < n; i++) {
//			System.out.print(b[i] + " ");
//		}
//		System.out.println();

		M.perm(0, 0, pm, ch, b);

	}

}