回溯法-求解部分和问题

题目内容：

给出N个正整数组成的数组A，求能否从中选出若干个，使他们的和为K。如果可以，输出："YES"，否则输出"NO"。

输入格式:

第1行：2个数N、K, N为数组的长度, K为需要判断的和(2 ≤N ≤ 20，1 ≤ K ≤ 10^9)

第2 到第 N + 1行：每行1个数，对应数组的元素A[i] (1 ≤ A[i]≤ 10^6)

输出格式：

如果可以，输出："YES"，否则输出"NO"。

样例输入

4 13

样例输出

YES

输入样例：

5 9

输出样例：

YES

题目分析：

本题与最小机器重量题类似，用while循环实现遍历2^n种情况。

代码如下

 1 #include<stdio.h>
 2 #define LEN 30
 3 int main()
 4 {
 5     int a[LEN];
 6     int b[LEN][LEN];//b[i][0]代表第i个数不取，b[i][1]代表第i个数被取 
 7     int p[LEN];
 8     int n,k;
 9     scanf("%d%d",&n,&k);
10     for(int i=1;i<=n;i++)
11     {
12         scanf("%d",&a[i]);
13         b[i][1]=a[i];
14         b[i][0]=0;
15     }    
16     int sum=0;
17     int t=1;
18     int q=0;
19     int sign=0;
20     while(t>0)
21     {
22         sum+=b[t][q];
23         if(sum==k)
24         {
25             sign=1;
26             break;
27         }
28         p[t]=q;
29         if(t==n)
30         {
31             if(q<1)
32             {
33                 q++;
34             }
35             else
36             {
37                 sum-=b[t][q];
38                 while(p[t]>=1)
39                 {
40                     t--;
41                     if(t<=0)
42                         break;
43                     sum-=b[t][p[t]];
44                     if(sum==k)
45                     {
46                         sign=1;
47                         break;
48                     }
49 
50                 }
51                 q=p[t]+1;
52             }
53         }
54         else
55         {
56             t++;
57             q=0;
58         }
59     }
60     if(sign)
61         printf("YES");
62     else
63         printf("NO");
64         
65     return 0;
66 }