hdu1258

给你两个数t,n

接下来输入n个数字

让你输出所有数字相加等于n的组合

4　　6　　4　　3　　2　　2　　1　　1

t　　 n

4

3+1

2+2

2+1+1

Sample Input

4 6 4 3 2 2 1 1 5 3 2 1 1 400 12 50 50 50 50 50 50 25 25 25 25 25 25 0 0

Sample Output

Sums of 4: 4 3+1 2+2 2+1+1 Sums of 5: NONE Sums of 400: 50+50+50+50+50+50+25+25+25+25 50+50+50+50+50+25+25+25+25+25+25 其实就是个简单的dfs，一开始我还以为什么背包问题，结果发现想太多； #include <iostream> using namespace std; int n,m; int a[15],lu[15]; int cnt = 0; void dfs(int k,int t); bool flag; int main() {int i,j;while(scanf("%d%d",&m,&n) && m){flag = false;for(i=0;i<n;++i)scanf("%d",a+i);printf("Sums of %d:\n",m);dfs(-1,m);if(!flag)printf("NONE\n");} } void dfs(int k,int t) {if(t == 0){flag = true;printf("%d",lu[0]);for(int i=1; i<cnt; ++i){printf("+%d",lu[i]);}printf("\n");return ;}if(t < 0)return ;for(int j=k+1; j<n; ++j){if(t >= a[j]){lu[cnt++] = a[j];dfs(j,t-a[j]);while(j < n-1 && a[j] == a[j+1]) //防止重复的元素进入j ++;cnt --;}} }

 

转载于:https://www.cnblogs.com/mltang/p/8728446.html

总结

以上是生活随笔为你收集整理的hdu1258的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。