hdu 1258 Sum It Up dfs暴搜

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2660 题意：一串数字中含有n个数字，给一个数字m，要求从串中找出任意个数字的组合，它们的和为m，把它们全部按题目要求的格式输出。 #include<cstring> #include<algorithm> #include<functional> #include<vector> using namespace std; const int maxn = 15; vector<int> v[1000]; int f[maxn],vis[maxn]; int fa[10000]; int t,n,num; void dfs(int sum,int k) { if(sum>=t) { if(sum==t) { for(int i=0;i<n;i++) if(vis[i]) v[num].push_back(f[i]); int flag=0; for(int i=0;i<num;i++) { int j=0; if(v[i].size()==v[num].size()) { for(;j<v[num].size();j++) if(v[i][j]!=v[num][j]) { break; } if(j==v[num].size()) { v[num].clear(); flag=1; break; } } } if(flag==0)num++; } return; } else { for(int i=k;i<n;i++) { if(!vis[i]) { vis[i]=1; dfs(sum+f[i],k+1); vis[i]=0; } } } } int main() { while(scanf("%d%d",&t,&n)&&(t||n)) { for(int i=0;i<num;i++) v[i].clear(); num=0; for(int i=0;i<n;i++) scanf("%d",&f[i]); sort(f,f+n,greater<int>() ); dfs(0,0); printf("Sums of %d:\n",t); if(num!=0) { for(int i=0;i<num;i++) { for(int j=0;j<v[i].size();j++) { if(j!=v[i].size()-1) printf("%d+",v[i][j]); else printf("%d",v[i][j]); } printf("\n"); } } else printf("NONE\n"); } }