本文主要是介绍poj 1564 Sum It Up -- DFS 递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给一个数 t ，以及 n 个数，求 n 个数中的几个数加起来的和为 t 的情况有多少种。
注意：题目要求相同的组合方式不能出现2次，即 “3 4 1 1 1 1 ” 的结果为：“1+1+1”。
思路：一个 for 循环遍历一遍，每个 i 表示以当前数为起点开始一次DFS递归，当所遍历的和为 t 时，输出该组合方式，如果大于 t 则返回，小于则往下递归。以二维数组保存已经输出过的数据，当又一次需要输出数据时，则需确认二维数组里没有改组数据（个人觉得还有更好的方法）。
#include<stdio.h>
#include<string.h>
int n,m,i,j,k,t,l;
int data[20],vis[20],res[20],rear,flag,judge,save[20][20],num,count;// res数组保存当前的进行遍历的数据，save 数组则保存已经输出过的数据
int dir[11]={1,2,3,4,5,6,7,8,9,10,11};
void dfs(int x,int sum)
{if(sum>t) {return;}if(sum==t){flag=0;for(l=0;l<num;l++){count=0;for(j=0;j<rear;j++)if(save[l][j] == res[j]) count++; if(count==rear) {flag=1;break;}}if(!flag){for(j=0;j<rear;j++)save[num][j]=res[j];num++;for(j=0;j<(rear-1);j++)printf("%d+",res[j]);printf("%d\n",res[rear-1]); judge=1; // judge 为 1 表示输出过数据，为 0 则表示没输出过，则输出 “NONE” }return;}for(k=0;k<n;k++) {x=x+1;if(x>=n) return; // 此处很关键！！！没加就WA，表示费解。if(x<n&&vis[x]==0){vis[x]=1;res[rear++]=data[x];dfs(x,sum+data[x]);rear--; // rear 表示 res 数组的长度，当递归返回时（已经输出过一组数据，或者 和 大于 t ），需要减 1 。vis[x]=0;}}
}
int main()
{while(scanf("%d%d",&t,&n)!=EOF && n!=0){for(i=0;i<n;i++)scanf("%d",&data[i]);printf("Sums of %d:\n",t);judge=0;num=0;memset(save,0,sizeof(save));for(i=0;i<n;i++) // for 循环遍历一遍{memset(vis,0,sizeof(vis)); // 每一个 i 都是一个新的开始，vis 及 res 数组需要初始化memset(res,-1,sizeof(res));vis[i]=1;rear=0;res[rear++]=data[i];dfs(i,data[i]);vis[i]=0;}if(!judge) printf("NONE\n");}return 0;
}这篇关于poj 1564 Sum It Up -- DFS 递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
