（深搜）Sum It Up -- poj --1564

链接：

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 <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, flag;

int a[], b[];

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 = ;

        sort(b, b + ans, cmp);

        for(int i = ; 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 + , ans + , sum + a[i]);

            while(i +  < m && a[i] == a[i + ])//去重

                ++i;

        }

    }

}

/*去重：
  例如：3 3 2 1 1
  为了防止出现 2+1
             2+1
  这样的重复数据

  刚看时我连去重的意思都弄错了，不知道是什么意思，还好调试了一遍知道了

*/

int main ()

{

    while(scanf("%d%d", &n, &m), n || m)

    {

        for(int i = ; i < m; ++i)

            scanf("%d", &a[i]);

        flag = ;

        sort(a, a + m, cmp);

        printf("Sums of %d:\n", n);

        dfs(, , );

        if(!flag)

            printf("NONE\n");

    }

    return ;

}