66 lines
1.4 KiB
C++
66 lines
1.4 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
|
|
int ans = 1e9;
|
|
vector<int> path;
|
|
vector<bool> visited;
|
|
vector<int> result;
|
|
bool detected = false;
|
|
int c[15][15];
|
|
|
|
void initc(int n){
|
|
for(int i = 0; i < n; i++){
|
|
c[i][0] = 1;
|
|
for(int j = 1; j <= i; j++){
|
|
//C(n, k) = C(n-1, k-1) + C(n-1, k)
|
|
c[i][j] = c[i-1][j-1] + c[i-1][j];
|
|
}
|
|
}
|
|
}
|
|
|
|
void dfs(vector<int>& path, vector<bool>& visited, int sum, int n, int currSum){
|
|
if(detected == true) return;
|
|
if(currSum > sum) return;
|
|
int s = path.size();
|
|
|
|
if(s == n){
|
|
int addup = 0;
|
|
for(int i = 0; i < s; i++){
|
|
addup += path[i] * c[s - 1][i];
|
|
}
|
|
//cout << addup << endl;
|
|
if(addup == sum) {
|
|
//result = result > path ? path : result;
|
|
result = path;
|
|
detected = true;
|
|
}
|
|
return;
|
|
}
|
|
|
|
for(int i = 1; i <= n; ++i){
|
|
if(!visited[i - 1]){
|
|
path.push_back(i);
|
|
visited[i - 1] = true;
|
|
dfs(path, visited, sum, n, currSum + i * c[n-1][path.size() - 1]);
|
|
visited[i - 1] = false;
|
|
path.pop_back();
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
|
|
int main(){
|
|
int n, sum;
|
|
cin >> n >> sum;
|
|
visited.resize(n, false);
|
|
initc(n);
|
|
dfs(path, visited, sum, n, 0);
|
|
for(auto& x: result){
|
|
cout << x << " ";
|
|
}
|
|
cout << endl;
|
|
return 0;
|
|
}
|