itdef

題意是給你一個(gè)N(1<=N<=10)

要求將1到N的數(shù)字進(jìn)行排列 然后進(jìn)行楊輝三角運(yùn)算

每行的數(shù)字等于上一行相同坐標(biāo)和上一行相同坐標(biāo)右邊的兩個(gè)數(shù)字之和

最后得到唯一的一個(gè)數(shù)字

現(xiàn)在給予N 和一個(gè)M

請問初始的N個(gè)數(shù)字該如何排列才能得到這個(gè)M
輸入
n m 
n為數(shù)字個(gè)數(shù) m為要求的最后的楊輝三角的和

輸出
一行數(shù)字使用空格隔開
為初始的N個(gè)數(shù)字的排列 如果有多個(gè)答案 輸出字典序最小的一個(gè)

樣例
Sample Input
4 16
Sample Output
3 1 2 4  (3 2 1 4 也是答案 但是它不是字典序最小的排列)

#include <iostream>

using namespace std;
/*
Sample Input
4 16
Sample Output
3 1 2 4
*/

const int N = 15;

int arr[N];
int used[N];
int n, m;

int check[N][N];

//暴力模擬楊輝三角的記錄
bool CheckArr() {
    for (int i = 0; i < n; i++) {
        check[0][i] = arr[i];
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            check[i][j] = check[i - 1][j] + check[i - 1][j + 1];
        }
    }

    if (check[n - 1][0] == m) return true;
    return false;
}

bool dfs(int idx)
{
    if (idx >= n) {
        if (CheckArr() == true) {
            for (int i = 0; i < n; i++) {
                cout << arr[i] << " ";
            }
            cout << endl;
            return true;
        }
        return false;
    }

    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) {
            used[i] = 1; arr[idx] = i;
            if (true == dfs(idx + 1)) return true;
            used[i] = 0;
        }
    }
    return false;
}


int main()
{
    cin >> n >> m;
    dfs(0);
    return 0;
}