部分和问题(DFS)

问题描述

对于给定的n个整数,从中选出若干数,使其和为k

输入

1
2
3
n=4
k=13
a = {1,2,4,7}

输出

1
Yes

解题思路

利用dfs遍历数组,类似于走迷宫问题

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int n=4;
int a[4] = {1,4,2,7};
int k = 15;

bool dfs(int i,int sum){
if (i==n) return sum==k;
if(dfs(i+1,sum)) return true;
if(dfs(i+1,sum+a[i])) return true;
}

int main() {
if(dfs(0,0)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}

本文标题:部分和问题(DFS)

文章作者:定。

发布时间:2017年8月23日 - 22时08分

本文字数:785字

原始链接:http://cocofe.cn/2017/08/23/部分和问题(DFS)/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。