[2018大华软件创新挑战赛]模拟赛第四题

 1 #include <stdio.h>
 2 
 3 int result[100000];
 4 int count;
 5 
 6 void combination(int* arr,int i,int cnt)
 7 {
 8         if(i >= cnt)
 9         {
10                 int sum = 0;
11                 for(int j=0; j<cnt; j++)
12                 {
13                         sum += arr[j];
14                 }
15                 for(int j=0; j<count; j++)
16                 {
17                         if(sum == result[j]) return;
18                 }
19                 result[count++] = sum;
20                 return;
21         }
22 
23         int temp = arr[i];
24         arr[i] = 0;
25         combination(arr,i+1,cnt);
26         arr[i] = temp;
27         combination(arr,i+1,cnt);
28 }
29 
30 int main()
31 {
32         int t = 0;
33         scanf("%d",&t);
34         while(t--)
35         {
36                 int n = 0;
37                 scanf("%d",&n);
38 
39                 int val[n];
40                 for(int i=0; i<n; i++)
41                 {
42                         scanf("%d",&val[i]);
43                 }
44 
45                 int num[n];
46                 int cnt = 0;
47                 for(int i=0; i<n; i++)
48                 {
49                         scanf("%d",&num[i]);
50                         cnt += num[i];
51                 }
52 
53                 int arr[n*cnt];
54                 cnt = 0;
55                 for(int i=0; i<n; i++)
56                 {
57                         for(int j=0; j<num[i]; j++)
58                         {
59                                 arr[cnt++] = val[i];
60                         }
61                 }
62                 printf("\n");
63                 combination(arr,0,cnt);
64                 printf("%d \n",count);
65         }
66 }