杭電 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;
}