1935-买装备-backtracking,dp

 1 

#include 
 2 
 3 long long s[20], x[20] = { 0 }, c,sum=0; int n;
 4 //回溯法解决子集和问题 ，子集中的那个数若存在则记为1，否则为0
 5 int backtrack(int t) {
 6     static int count=0;
 7     int i;
 8     if (t == n) {
 9         if (sum == c)
10         {
11             count++;
12             return count;
13         }
14     }
15     else
16     {
17         //去除掉第1,2,3，...个元素后满足的情况，选择分支1
18         sum += s[t];
19         x[t] = 1;
20         backtrack(t + 1);
21         //不去除时满足的情况，选择分支2
22         x[t] = 0;
23         sum -= s[t];
24         backtrack(t + 1);
25         return count;
26     }
27 
28 }
29 int main()
30 {
31     int count=0;
32     scanf("%d%lld", &n, &c);
33     for (int i = 0; i < n; i++) {
34         scanf("%lld", &s[i]);
35         x[i] = 0;
36     }
37     count=backtrack(0);
38     printf("%d", count);
39     return 0;
40 }