链接：

http://poj.org/problem?id=1564

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88230#problem/F

 

给了一个数 m，给一个由 n 个数组成的数组 a[] ， 求和为 m 的 a[] 的子集

 

pos 代表的是搜到第 pos 个元素，ans 代表的是 b[] 数组中存的第 ans 个数 

我一定要学会深搜！！！

 

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n, m, flag;int a[11000], b[11000];int cmp(int a, int b){    return a > b;}
        
       
      
     

///pos 代表的是搜到第 pos 个元素，  ///ans 代表的是 b[] 数组中存的第 ans 个数, b[] 数组里存的是和为 sum 的 void dfs(int pos , int ans, int sum)

{    if(sum == n)    {        flag = 1;        sort(b, b + ans, cmp);        for(int i = 0; i < ans; ++i)        {            if(!i)                printf("%d",b[i]);            else if(i)                printf("+%d",b[i]);        }        printf("\n");        return;    }    for(int i = pos; i < m; ++i)    {        if(sum + a[i] <= n)        {            b[ans] = a[i];            dfs(i + 1, ans + 1, sum + a[i]);            while(i + 1 < m && a[i] == a[i + 1])//去重                ++i;        }    }} /*去重：   例如：3 3 2 1 1   为了防止出现 2+1              2+1   这样的重复数据   刚看时我连去重的意思都弄错了，不知道是什么意思，还好调试了一遍知道了*/int main (){    while(scanf("%d%d", &n, &m), n || m)    {        for(int i = 0; i < m; ++i)            scanf("%d", &a[i]);        flag = 0;        sort(a, a + m, cmp);        printf("Sums of %d:\n", n);        dfs(0, 0, 0);        if(!flag)            printf("NONE\n");    }    return 0;}