POJ-1564 dfs

 1  #include"cstring"
 2  #include"cstdio"
 3  const int maxn=100+5;
 4  int nux[maxn];
 5  int nua[maxn];//解的集合 
 6  int t;//t为和 
 7  int n;//n为元素个数 
 8  bool flag;//判断是否有解 
 9  void dfs(int sum,int cur,int k){//sum剩余的大小 k为下标，cur为元素个数 
10      if(sum==0){
11          flag=false;//证明有解 
12          for(int i=0;i<cur;i++)
13              if(i==0)
14                  printf("%d",nua[i]);
15              else
16                  printf("+%d",nua[i]);
17          printf("
");
18          return;
19      }
20      for(int i=k;i<n;i++){
21          if(i==k||nux[i]!=nux[i-1]&&sum>=nux[i]){//判断是否重叠 
22              nua[cur]=nux[i];
23              dfs(sum-nux[i],cur+1,i+1);
24          }
25     }
26  }
27  int main(){
28      while(scanf("%d%d",&t,&n)!=EOF){
29          if(n==0&&t==0)    break;
30          for(int i=0;i<n;i++){
31              scanf("%d",&nux[i]);
32          }
33          flag=true;
34          printf("Sums of %d:
", t);
35          dfs(t,0,0);
36          if(flag)
37              printf("NONE
");
38      }
39      return 0;
40  }