求和问题(DFS)

输入:

n=4

a={1,2,4,7}

k=13

输出:

YES

输入:

n=4

a={1,2,4,7}

k=13

输出:

选出若干数,使它们的和恰好为k

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <ctype.h>
 7 #include <iomanip>
 8 #include <queue>
 9 #include <stdlib.h>
10 using namespace std;
11  
12 int a[55];
13 int n,k;
14 //已经从前i项得到了和sum,然后对于i项之后的进行分支
15 bool dfs(int i,int sum)
16 {
17     //如果前n项都计算过了,则返回sum是否与k相等
18     if(i==n)  return sum==k;
19     //不加a[i]的情况
20     if(dfs(i+1,sum))  return true;
21     //加上a[i]的情况
22     if(dfs(i+1,sum+a[i]))  return true;
23     //无论是否加上a[i]都不能凑成k就返回false
24     return false;
25 }
26 
27 void solve()
28 {
29     if(dfs(0,0)) printf("YES
");
30     else   printf("NO
");
31 }
32 
33 int main()
34 {
35     cin>>n;
36     for(int i=0;i<n;i++){
37         cin>>a[i];
38     }
39     cin>>k;
40     solve();
41 }

<<挑战程序设计竞赛>>读后感