https://www.luogu.org/problemnew/show/P1118
看的出来是个dfs 本来打算直接从下到上一顿搜索 但是不会
看了题解才知道系数是个杨辉三角.......
这样就好写了 但是还是踩了一些坑
一开始只有70分 是因为我最后再把a[i]求和 再判断的 改了之后80分......
加了一个剪枝:
if(s>sums) return;
如果当前和大于sum就返回
成功AC
#include<bits/stdc++.h> using namespace std; int n,sums,a[15],flag,yh[15][15],vis[15],s; void dfs(int t) //t标记当前确定了几个数 { int i; if(s>sums) return; if((t==n+1)&&s==sums) { //cout<<a[0]; for(i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; exit(0); } //else { for(i=1;i<=n;i++) { if(!vis[i]) { vis[i]=1; a[t]=i; s+=yh[n][t]*a[t]; dfs(t+1); s-=yh[n][t]*a[t]; vis[i]=0; } } } } int main() { int i,j; cin>>n>>sums; for(i=1;i<=n;i++) { yh[i][1]=1; yh[i][i]=1; } for(i=2;i<=n;i++) for(j=2;j<i;j++) { yh[i][j]=yh[i-1][j-1]+yh[i-1][j]; //cout<<yh[i][j]; } dfs(1); }