首页 > 代码库 > 部分和问题 (DFS)

部分和问题 (DFS)

来源:《挑战程序设计竞赛》

题目描述:

给定整数n个,判断是否能从中选出若干数,使它们的和恰好为k。

输入 n,k,array[0~n-1];

输出 Yes或者No。

 

思路:

从a1开始按顺序决定每个数加还是不加,在全部n个数都决定后在判断它们的和是不是k即可。

每个点都分出两种状态:加上当前数或者不加,dfs函数里主要完成:{状态的两种延伸(加上当前行数或者不加);当前状态的描述(判断当前和是否为k);}

代码:

#include <iostream>
#include <cstring>
#define MAXN 101
#define fooor(a,b) for(int i=a;i<b;i++)
using namespace std;
int ar[MAXN];
int n, k;
bool dfs(int i, int sum) {
    if (i == n) return sum == k;
    if (dfs(i + 1, sum)) return true;
    if (dfs(i + 1, sum + ar[i])) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(false);
    while (cin >> n >> k) {
        memset(ar, 0, sizeof(int));
        fooor(0, n) { cin >> ar[i]; }
        cout << (dfs(0, 0) ? "Yes" : "No") << \n;
    }
    return 0;
}

部分和问题 (DFS)