POJ 1564 Sum It Up dfs

题意：给你一个数sum，然后再给你一个数n，再给你n个数，从n个数中找出一些数，让这些数的和是n。所给的n个数是递减的，让输出的结果也是按照递减的形式输出。
思路：由于n最大为12，所以很明显可以暴力搜出所有的情况，然后判断和是否为sum，如果为sum，则输出即可。需要注意两点的是：首先有一个去重的过程，我的处理是把合适的全部存在一个vector里面，然后找到合适的去vector里面逐个判断是否和某一个重复，若都不重复，则符合题意，并且把这个也记录到vector里面。因为最后要从大到小输出，所以我又用了一个结构体存下来答案，最后又对结构体排了下序，之后的就是正解了。
代码：
[cpp] 
#include <iostream> 
#include <string.h> 
#include <cstdio> 
#include <algorithm> 
#include <vector> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
struct add{ 
    int ans[15]; 
    int size; 
}aa[100005]; 
int num[15],flag[15],num2[15],sum,n,numvv,numaa; 
bool isok; 
vector<int> vv[5005]; 
bool fun(int cnt){ 
    bool is = false; 
    for(int i  = 0; i < numvv; ++i){ 
        is = false; 
        if(vv[i].size() == cnt){ 
            for(int j = 0 ;j < vv[i].size(); ++j){ 
                if(num2[j] != vv[i][j]){ 
                  is = true; 
                  break; 
                } 
            } 
            if(!is) 
                return false; 
        } 
    } 
    return true; 
} 
void dfs(int begin,int id,int cnt){ 
    if(id == cnt){ 
      int ss = 0; 
      for(int i = 0; i < cnt; ++i) 
          ss += num2[i]; 
      if(ss == sum && fun(cnt)){ 
        isok = true; 
        aa[numaa].size = cnt; 
        for(int i = 0; i < cnt; ++i){ 
          aa[numaa].ans[i] = num2[i]; 
        } 
        numaa++; 
        for(int i = 0; i < cnt; ++i){ 
            vv[numvv].push_back(num2[i]); 
        } 
        numvv++; 
      } 
      return; 
    } 
    for(int i = begin; i < n; ++i){ 
        if(!flag[i]){ 
           num2[id] = num[i]; 
           flag[i] = true; 
           dfs(i,id+1,cnt); 
           flag[i] = false; 
        } 
    } 
} 
bool cmp(add a,add b){ 
    for(int i = 0; i < 13; ++i){ 
       if(a.ans[i] > b.ans[i]) 
           return true; 
       else if(a.ans[i] < b.ans[i]) 
           return false; 
    } 
} 
int main(){ 
    //freopen("1.txt","r",stdin); 
    while(scanf("%d%d",&sum,&n) && n){ 
       CLR(num,0); 
       CLR(flag,0); 
       CLR(vv,0); 
       numvv = 0; 
       numaa = 0; 
       for(int i = 0; i < n; ++i) 
           scanf("%d",&num[i]); 
       isok = false; 
       printf("Sums of %d:\n",sum); 
       for(int i = 1; i <= n; ++i){ 
          CLR(flag,0); 
          CLR(num2,0); 
          dfs(0,0,i); 
       } 
       if(!isok) 
           printf("NONE\n"); 
       else{ www.zzzyk.com
         sort(aa,aa+numaa,cmp); 
         for(int i = 0; i < numaa; ++i){ 
             int len = aa[i].size; 
             for(int j = 0; j < aa[i].size - 1; ++j){ 
                printf("%d+",aa[i].ans[j]); 
             } 
             printf("%d\n",aa[i].ans[len-1]); 
         } 
       } 
    } 
    return 0; 
} 

作者：wmn_wmn

补充：软件开发 , C++ ,