思路：设一开始的n个数为a1、a2、a3...an，一步一步合并就可以用a1..an表示出最后剩下来的数，不难发现其中a1..an的系数恰好就是第n层杨辉三角中的数。所以我们可以先处理出第n层杨辉三角中的数，然后根据这一层中的数搜索即可。
#include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<string> #include<sstream> #include<cstring> using namespace std; int n=0,sum=0,t[20],ans[20]; bool flag=false,book[20];//flag表示是否已经得出答案 void dfs(int x,int y) { //如果已经得出答案或者当前的和大于给定的和，就结束搜索 if(flag||y>sum) return; if(x>n)//表示已经搜完 { if(y==sum)//如果当前答案等于给定的和 { for(int i=1;i<=n;i++) printf("%d ",ans[i]);//就输出答案 flag=true;//标记已经得出答案，因为数是从小到大枚举的，所以第一个出现的答案一定是字典序最小。 } return; } for(int i=1;i<=n;i++)//枚举当前数 if(!book[i])//如果这个数还没被用过 { book[i]=true;//标记 ans[x]=i;//记录 dfs(x+1,y+t[x]*i);//搜索 ans[x]=0;//回溯 book[i]=false;//回溯 } } int main() { scanf("%d%d",&n,&sum); t[1]=1; for(int i=2;i<=n;i++)//预处理第n层出的杨辉三角 for(int j=i;j>=1;j--) t[j]+=t[j-1]; dfs(1,0);//搜索 return 0; }