杭电 HDU 1258 Sum It Up

问题：
先输入两个数，一个和sum，一个数据个数n，然后接着n个数为具体的数据，求n个数里面的数相加为sum的组合并输出。如果没有则输出：NONE

限制和剪枝：
1、输出不能有重复的情况，即只能是不同的组合。

代码里面那个判重关键理解了好久。。。感觉还是半懂。。T_T 。。
如果没有那两行代码，输出的就有很多重复情况。

一开始不知道怎么判重，后来想到字典树，又没有想到字典树怎么表示，后来发现可以用二维数组把所有情况全存着，然后最后输出时再进行判重，不过感觉好麻烦，还要开辟一个二维数组存所有
情况，然后再开一个输出而为数组，在所有情况的数组中要和输出数组进行比较，看是否已经存在。
感觉这种方法好麻烦，而且时间复杂度应该也比较高，但是在百度的时候发现好像有人这样过了。。。反正看到有人用这种方法贴出了代码。。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int a[500],out[500];
int sum,n,p;

void Dfs(int nowsum, int k, int start)
{
    int nextsum,i;
    int x;
    if(nowsum > sum)
    {
        return ;
    }
 //   printf("k:%d nowsum:%d\n",k,nowsum);
    if(nowsum == sum)
    {
        p++;     //标记有存在的组合
        printf("%d",out[0]);
        for(i = 1; i < k; i++)
        {
            printf("+%d",out[i]);
        }
        printf("\n");
        return ;
    }
    x = -1;    //初始化起点位置(判重关键)
    for(i = start; i < n; i++)
    {
 //       printf("i:%d x:%d a[i]:%d\n",i,x,a[i]);
        if(x != a[i])    //判重关键
        {
            x = a[i];
            out[k] = a[i];
            nextsum = nowsum + a[i];
            Dfs(nextsum,k+1,i+1);
        }

    }
    return ;
}

int main()
{
    int i,nowsum,k;;
    while(scanf("%d%d",&sum,&n)&&sum||n)
    {
        nowsum = k = p = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
        }
        printf("Sums of %d:\n",sum);
        Dfs(nowsum,k,0);
        if(p == 0)
        {
            printf("NONE\n");
        }
    }

    return 0;
}

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

上一个：HDU2844:Coins(多重背包)
下一个：HDU1171：Big Event in HDU(多重背包)