如题
如果直接全排列进行判断是会有数据超时的,观察此题的样例数据可以发现与杨辉三角有关系,如下图所示,以n=4为例,在字母第四层的系数与左边数字的乘积的和即1*3+3*1+3*2+1*4刚好与结果是相等的,故我们可以根据题目输入的n为大小构建一个杨辉三角,然后对递归函数进行剪枝就可以pass了.
#include<bits/stdc++.h>
using namespace std;
int n,sum,b[15],a[15],f[15],w[15];
int dd[15][15];
bool flag;
#define endl '\n'
void permutation(int depth,int s) {if(s>sum)//比sum大,直接返回上一层,节约时间return ;if(depth>n) {if(s==sum) {for(int i=1; i<=n; i++)cout<<b[i]<<" ";exit(0);//输出后直接结束}return ;}for(int i=1; i<=n; i++) {if(!f[i]) {f[i]=1;b[depth]=i;permutation(depth+1,s+dd[n][depth]*i);//第二个参数为当前数i与杨辉三角最后一层系数的乘积的和f[i]=0;//回溯}}
}
int main() {cin>>n>>sum;dd[1][1]=1;for(int i=2; i<=n; i++)for(int j=1; j<=i; j++)dd[i][j]=dd[i-1][j]+dd[i-1][j-1];permutation(1,0);return 0;
}记录一下,日后回看