深度优先搜索(DFS)——部分和问题

对于深度优先搜索,这里有篇写的不错的博客: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;
}

上一篇:android 搭建开发环境


下一篇:[HTML/HTML5]2 CSS样式表设置