题解

#include <iostream>
#include <vector>
using namespace std;

int n, sum;
vector<vector<int>> pascalTriangle;
vector<int> ans;
vector<bool> used;

void generatePascalTriangle() {
    // 生成n层的杨辉三角
    pascalTriangle.resize(n+1);
    for(int i=1; i<=n; ++i) {
        pascalTriangle[i].resize(i+1);
        pascalTriangle[i][1] = pascalTriangle[i][i] = 1;
        for(int j=2; j<i; ++j) {
            pascalTriangle[i][j] = pascalTriangle[i-1][j-1] + pascalTriangle[i-1][j];
        }
    }
}

bool dfs(int step, int currentSum) {
    if(step > n) {
        return currentSum == sum;
    }
    for(int i=1; i<=n; ++i) {
        if(!used[i]) {
            int newSum = currentSum + i * pascalTriangle[n][step];
            if(newSum > sum) continue; // 剪枝
            used[i] = true;
            ans[step] = i;
            if(dfs(step+1, newSum)) return true;
            used[i] = false;
        }
    }
    return false;
}

int main() {
    cin >> n >> sum;
    generatePascalTriangle();
    ans.resize(n+1);
    used.resize(n+1, false);
    if(dfs(1, 0)) {
        for(int i=1; i<=n; ++i) {
            cout << ans[i] << " ";
        }
    }
    return 0;
}