White-book-example

给定一组数，判断是否可以从中取出若干数，是他们的和恰好为一个数。
Example:
input
4 13
2 3 4 7
ouput
Yes

每个数都会有两个状态，加上或者不加上，这组样例中有四个数，每个数两个状态，也就是说最后的加起来的结果会有2的4次方(16)种。

Codes

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10000];
bool dfs(int i,int sum)
{
    if(i==n)
    {
//      puts("mmp");
        return sum==k;
    }   
    if(dfs(i+1,sum))
    {
//      puts("a");  
        return 1;
    }
    if(dfs(i+1,sum+a[i]))
    {
 //     puts("b");
        return 1;   
    }   
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    if(dfs(0,0)) puts("Yes");
    else puts("No");
    return 0;
}

只看代码会很难理解，一重一重的递归，但这还只是最简单的一种。为了更好的让自己理解，我将这个样例的所有情况都列了出来。

DFS(0,0)
    DFS(1,0)
        DFS(2,0)
            DFS(3,0)
                DFS(4,0) return 0      
                DFS(4,7) return 0
            DFS(3,4)
                DFS(4,4) return 0
                DFS(4,11) return 0
        DFS(2,3)
            DFS(3,3)
                DFS(4,3) return 0
                DFS(4,10) return 0
            DFS(3,7)
                DFS(4,7) return 0
                DFS(4,14) return 0
    DFS(1,2)
        DFS(2,2)
            DFS(3,2)
                DFS(4,2) return 0
                DFS(4,9) return 0
            DFS(3,6)
                DFS(4,6) return 0
                DFS(4,13) return 0
        DFS(2,5)
            DFS(3,5)
                DFS(4,5) return 0
                DFS(4,12) return 0
            DFS(3,9)
                DFS(4,9) return 0
                DFS(4,16) return 0

我又将这16种情况，用图的方式表示了出来

                                    0
                                2       0
                            5   2       3   0
                    9   5   6   2       7   3   4   0
    16  9   12  5   13  6   9   2       14  7   10  3   11  4   7   0

这时我发现程序跟画出来的是一模一样的。

可是还是不很理解，于是我运行起来程序，并且在每次递归中加入了可以看到的元素，输出a，b或者mmp啊什么的。一起来看看效果
input:
4 13
2 3 4 7

input:
4 0
2 3 4 7

mmp代表的个数就是出现sum==k的时候前面进行的递归的次数，a代表的是第i位的数状态是不加，b代表的是第i位的数状态是加

也就这样了，DFS慢慢来，这样跑程序我觉得会加深理解啊哈🎈。