DFS—找数字和

题目： http://www.fjutacm.com/Contest.jsp?cid=860#P3

 此题的三种做法，都是递归。

代码

 一，

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
using namespace std;
int map[30], vis[30], way[30];
int n, k;
queue<int>q;
int flag = 0, sum = 0;
void DFS(int j,int res)
{
	if (flag == 1)
		return;
	if (sum > k)
		return;
	if (sum == k)
	{
		flag = 1;
		printf("YES
");
		for (int i = 0; i < res ; i++)
			printf("%d ", way[i]);
		puts("");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		if (vis[i] == 0)
		{
			vis[i] = 1;
			way[res] = map[i];
			sum += map[i];

			DFS(i + 1, res + 1);

			vis[i] = 0;
			sum -= map[i];
		}
	}
}
int main(void)
{
	while (scanf("%d%d", &n, &k) != EOF)
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &map[i]);
		}
		DFS(0, 0);
		if (flag == 0)
			printf("NO
");
		memset(way, 0, sizeof(way));
		memset(vis, 0, sizeof(vis));
		flag = 0, sum = 0;	
	}
}

① 这种需要记录路径的，好像只能利用递归的回溯来记录，

如果是使用栈的话，因为要同时压好几个数进栈，如果直接记录的话，就把同级的结点给记录上了，这样就错了，

但如果是递归的话，因为不用压栈，他直接回溯回来使用数据，自然不用把数据压入栈中。

现在我也不知道有没有办法可以解决这个问题，就只能用递归。

（补充：之前说错了，原来还没学 链式前向星，图的存取是可以用这个的。而 BFS 要记录路径的话，运用 结构体设两个变量 id 和 from ，用链表的思想就可以做到了，详见

https://www.cnblogs.com/asdfknjhu/p/12499112.html ）

② 注意回溯时，要把改变的条件改回来。

像这一段，

i 是函数传参时直接改变，回溯时就自己变回来了，不用改变

而数组 vis 和 数字 sum 不是 参数，无论你函数调用多少次，他还是不会变，所以，必须在它回溯时给减回来

if (vis[i] == 0)
{
　　vis[i] = 1;
　　way[res] = map[i];
　　sum += map[i];
　　DFS(i + 1, res + 1);
　　vis[i] = 0;
　　sum -= map[i];
}

二，

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
stack<int>s;
int n, k, a[30];
bool DFS(int i, int sum)                     
{
    if (sum > k)
        return false;
    if (i == n)                                   
        return k == sum;
    if (DFS(i + 1, sum + a[i])) //选 a[i]
    {
        s.push(a[i]);
        return true;
    }
    if (DFS(i + 1, sum))   //不选 a[i]
        return true;
    return false;
}
int main(void)
{
    while (scanf("%d%d", &n, &k) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        if (DFS(0, 0))
        {
            printf("YES
");
            while (!s.empty())
            {
                printf("%d ", s.top());
                s.pop();
            }puts("");
        }
        else
            printf("NO
");
    }
    return 0;
}

① 就是看到这个递归式才想起来这题的判断可以用 dp 做，不过储存路径还得是 DFS 才可以

三，递归的返回值

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool state[25];
int a[25], k;
int dfs(int sum, int n)
{
    if (sum == k)   // 找到了，开始回溯
        return 1;
    if (n == 0)   // 找完了，开始回溯
        return 0;

    while (n)
    {
        if (dfs(sum + a[n], n - 1))   // 如果是找到了结果的回溯，才记录
        {
            state[n] = 1;
            return 1;
        }
        n--;
    }
    
}
int main(void)
{
    int i, flag, n;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        memset(state, 0, 25);
        for (i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        if (dfs(0, n))
        {
            printf("YES
");
            for (i = 1, flag = 0; i <= n; i++)
                if (state[i])
                    printf("%d ", a[i]);
            printf("
");
        }
        else
            printf("NO
");
    }
    return 0;
}

缺点：

如果是用递归的返回值来判定要不要记录数据的话，

那么此种方法只试用于只有一条路的时候，

因为一旦你找到了正确的一条路径，就他就一直 return 到结束。

优点：

也不知道算不算优点，就是此种方法记录的路径于正常模板所记录的是反过来的

此种 是从结束条件开始记录的

模板 是从开始条件开始记录的

=========== ===== ============= ============ ======================== ===== 

青玉案·元夕　　宋 辛弃疾

东风夜放花千树，更吹风，星如雨。宝马雕车香满路，凤箫声动，玉壶光转，一夜鱼龙舞。

蛾儿雪柳黄金缕。笑语盈盈暗香去。众里寻他千百度，蓦然回首，那人却在，灯火阑珊处。