P1036 选数

题目描述
已知 nn 个整数 x1,x2,…,xn
，以及11个整数kk(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34。

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29

输入格式
键盘输入，格式为：

n,k(1≤n≤20,k<n)

x_1,x_2,…,x_n (1<=Xi<=5000000)

输出格式
屏幕输出，格式为： 11个整数（满足条件的种数）。

输入输出样例
输入
4 3
3 7 12 19
输出
1

 1 解法：
 2 
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 int data[21];
 6 int book[21];
 7 int n,k;
 8 int Sum=0;//和 为 素数的个数
 9 int sum=0;
10 void dfs(int cnt,int start){//两个参数，一个 用来 记录 选了多少个数字了cnt,另一个 start是每次搜索新开始的索引，
11     if(cnt>k) return ;//超过了统计的个数，返回
12     if(cnt==k){
13         for(int i=2;i<=sqrt(sum);i++){//检查是否是素数
14             if(sum%i==0){
15                 return ;
16             }
17         }
18         Sum++;//是素数， 个数+1
19         return ;
20     }
21     for(int i=start;i<n;i++){//主要
22         if(book[i]==0){
23             book[i]=1;//标记 被选上了
24             sum+=data[i];//sum加上这个数据
25             cnt++;//选择的个数加1
26             dfs(cnt,i+1);//这样写,cnt,sum不用再恢复了,就算不满足，仍然是原来的数
27             cnt--;//恢复 选择的个数  -1
28             book[i]=0;//取消被选的这个数字
29             sum-=data[i];
30         }
31     }
32     return ;
33 }
34 int main()
35 {
36     /*思路：不知道数据 Xi都是一样的会怎样
37         1:用data数组存数据,book 数组 标记 是否 选中
38         2:两个参数，一个 用来 记录 选了多少个数字了cnt,
39         3:另一个 start是每次搜索新开始的索引，
40         4:递归 回溯 求解，
41 */
42     cin>>n>>k;
43     for(int i=0;i<n;i++){
44         cin>>data[i];
45         book[i]=0;
46     }
47     dfs(0,0);//已经选了0个，从0开始的遍历
48     cout<<Sum<<endl;
49     return 0;
50 }

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int data[21];
 4 int n,k;
 5 int Sum=0;//和 为 素数的个数
 6 void dfs(int cnt,int start,int sum){//两个参数，一个 用来 记录 选了多少个数字了cnt,另一个 start是每次搜索新开始的索引，
 7     if(cnt>k) return ;//超过了统计的个数，返回
 8     if(cnt==k){
 9         for(int i=2;i<=sqrt(sum);i++){//检查是否是素数
10             if(sum%i==0){
11                 return ;
12             }
13         }
14         Sum++;//是素数， 个数+1
15         return ;
16     }//从新的地方开始，
17     for(int i=start;i<n;i++){//主要从新的索引 开始；不选择标记  因为  都是临时性的遍历，副本数据并没有更新，只是dfs传入的数据遍历
18         dfs(cnt+1,i+1,sum+data[i]);//这样写,cnt,sum不用再恢复了,就算不满足，仍然是原来的数
19     }
20     return ;
21 }
22 int main()
23 {
24     /*思路：不知道数据 Xi都是一样的会怎样
25         1:用data数组存数据,book 数组 标记 是否 选中
26         2:两个参数，一个 用来 记录 选了多少个数字了cnt,
27         3:另一个 start是每次搜索新开始的索引，
28         4:递归 回溯 求解，
29 */
30     cin>>n>>k;
31     for(int i=0;i<n;i++){
32         cin>>data[i];
33     }
34     dfs(0,0,0);//已经选了0个，从0开始的遍历,sum=0
35     cout<<Sum<<endl;
36     return 0;
37 }