对于深度优先搜索,这里有篇写的不错的博客:DFS算法介绍 。总得来说是从某个状态开始,不断的转移
状态知道无法转移,然后回到前一步
的状态.如此不断的重复一直到找到最终的解。根据这个特点,常常会用到递归。
应用:部分和问题
【题目链接:NYOJ-1058】
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
//部分和问题:
const int maxn = 22;
stack<int>v;
int a[maxn];
int n, m, i, j, k;
bool dfs(int i = 0, int sum = 0) //已经从前i项得到了和sum,然后对于i项之后的进行分支
{
//停止条件 :如果前n项都计算过了,则返回sum是否与k相等
if (i == n) return sum == k;
//选择加或不加a[i]
//不加a[i]的情况
if (dfs(i + 1, sum)) return true;
//加上a[i]的情况
if (dfs(i + 1, sum + a[i]))
{
//若执行该条件,就说明该a[i]符合条件
v.push(a[i]);//压栈
return true;
}
return false; //无论是否加上a[i]都不能凑成k就返回false;
}
int main() {
while (~scanf("%d%d", &n, &k))
{
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
if (dfs())
{
printf("YES\n");
while (!v.empty()) //把 满足dfs函数中的数 全部取出(从上往下)
{
int x = v.top();
printf("%d ", x);
v.pop();
}
printf("\n");
}
else
printf("NO\n");
}
return 0;
}