HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)]

点我挑战题目

从零开始DFS

HDOJ.1342 Lotto [从零开始DFS(0)] — DFS思想与框架/双重DFS

HDOJ.1010 Tempter of the Bone [从零开始DFS(1)] —DFS四向搜索/奇偶剪枝

HDOJ(HDU).1015 Safecracker [从零开始DFS(2)] —DFS四向搜索变种

HDOJ(HDU).1016 Prime Ring Problem (DFS) [从零开始DFS(3)] —小结：做DFS题目的关注点

HDOJ(HDU).1035 Robot Motion [从零开始DFS(4)]—DFS题目练习

HDOJ(HDU).1241 Oil Deposits(DFS) [从零开始DFS(5)] —DFS八向搜索/双重for循环遍历

HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)] —DFS双重搜索/去重技巧

HDOJ(HDU).1045 Fire Net [从零开始DFS(７)]—DFS练习/check函数的思想

题意分析

每组数据给出要凑出的目标数字num和数字个数n，然后依次给出n个数字。要求从n个数字中选出若干个数字，是的数字之和为nun。重复的组合只输出一次。

和之前做过的选数字的题目类似，也可以采用DFS的思想来做。这道题与HDOJ.1342 Lotto [从零开始DFS(0)]及其的相似：每个数字有2种选择，选/不选，只要我选择的这些数字的和为num就行了。但是不难想到会有重复的组合出现，例如给出的样例3：

400 12 50 50 50 50 50 50 25 25 25 25 25 25

要求从12个数字中选择出若干数字使得总和为400，我们可以发现选择6个50和4个25即可。那么若按照HDOJ.1342的思想，选/不选，问题就会出现：要从6个25中选4个25，会有C（6,4）中情况，也就是说最后的结果会多出11组相同的解。这显然不符合题意。

问题的关键在于如何去重，最先想到也是最容易想到的就是把每组解保存下来，如果遇到重复的只输出一组即可。很明显这种方法实现起来耗费的工程量是巨大的，非常麻烦。回到DFS的核心：递归。我们对于递归做出一些约束，当满足一定条件时，下面搜索的解会造成重复，就终止递归。这样得到的解，均是非重复的。关键就是找到这样的条件，或者说为递归创造这样的条件。

上代码。

代码总览

/*

    Title:HDOJ.1258

    Author:pengwill

    Date:2017-2-8

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int num,n,pos;

int a[15],b[15];

bool judge = false;

void output(int depth)

{

    for(int i =0 ;i< depth; ++i)

        if(!i) printf("%d",b[i]);

        else printf("+%d",b[i]);

    printf("\n");

}

void dfs(int depth,int sum,int pos)

{

    if(sum == num) {judge = true;output(depth); return;}

    if(sum>num) return;// 超出了 终止递归

    if(pos>=n) return; //选择的数的位置超出数据范围

    b[depth] = a[pos];

    dfs(depth+1,sum+a[pos],pos+1);

    while(pos+1<n&&a[pos] == a[pos+1]) pos++;//关键

    dfs(depth,sum,pos+1);

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d%d",&num,&n) && num){

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

        for(int i = 0; i<n; ++i) scanf("%d",&a[i]);

        judge = false;

        dfs(0,0,0);

        //output

        if(judge == false) printf("NONE\n");

    }

    return 0;

}

还是按照HDOJ.1342 Lotto [从零开始DFS(0)]中写到的双重DFS的办法（即选/不选的思想），解决此题。

递归边界：当数字的和为num时，或者和超出了num，或者要选择的数字位置超出了n，终止搜索。

关键是下面这几句。

    dfs(depth+1,sum+a[pos],pos+1);

    while(pos+1<n&&a[pos] == a[pos+1]) pos++;//关键

    dfs(depth,sum,pos+1);

首先是默认选择了pos这个位置的数字然后进行dfs。下面一个while循环表示如果下一个待选数字和本位置的待选数字一样的话，就跳过，一直跳到下一个待选数字不同的位置。如样例3：

400 12 50 50 50 50 50 50 25 25 25 25 25 25

就会从第一个50一直跳到最后一个50（下一个数字是25）。貌似看起来得不到正确结果，当然在第一层dfs不选择50的情况是没有正确解的。不放我们看一下下一层dfs，即选择了第一个50后的dfs。

进入第二层dfs依旧会有2种选择，要么选择第二个50，要么后续的50一个都不选。当然这时候一个50都不选的情况也是没有正确解的，继续看第三层。

进入第三层dfs还是会有2种选择，要么选择第三个50，要么后续的50一个都不选。但让后续50一个都不选的情况也没有正确解。

…………

依次类推，不难发现，这条while语句的作用就是：营造单一的选1个50，选2个50，选3个50这样的情况，从而避免了重复解的出现。