先一起看看题吧：
已知 nn 个整数 x1,x2,…,xn，以及11个整数k(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)
x1,x2,…,xn (1≤xi?≤5000000)
屏幕输出，格式为： 1个整数（满足条件的种数）。
4 3 3 7 12 19
1
这道题（坑了我3天）可以用递归......（放了一学期才搞懂的递归）
如果你也不懂递归..后面会写递归的学习心得和总结
解题思路：
所以只需要用递归来枚举，然后判断质数。
代码可分为3部分：
1.判断质数（）
{
循环%
if（是）return true；
else return false；
}
2.递归（深搜）枚举（）
{
先判断当前找的数是否大于k；
if（是）判断质数，ans++，return；
else 循环枚举
}
3.输入输出...
然后上完整代码 ：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 //#define ISA_XR 5 using namespace std; 6 int a[25],ans,n,k,s; 7 //a数组存每个数；ans存满足条件的个数；s 存枚举的k个数的和； 8 bool judge(int s) 9 { 10 if(s == 2) return true; //特殊质数 2 11 for(int i = 2;i <= sqrt(s);i++) 12 { 13 if(s % i == 0) 14 { 15 return false; 16 } 17 } 18 return true; 19 } 20 //判定 s 是否为质数 21 22 void search(int x,int y) // x 即当前找到的（要求和的）个数，y即当前找到的最后一个数a[y]位置（下标） 23 { 24 if(x > k) // 若已经找到 k 个数 就判断一波 s 25 { 26 if(judge(s)) ans++; //满足条件（是质数）ans++ 27 return ;//回到上一层“删除 ”a[y] 再枚举下一个数 28 } 29 for(int i = y + 1;i <= n;i++) 30 { 31 s += a[i];//求和。。。 32 search(x + 1,i);//再搜 x要++ 33 s -= a[i]; //回溯 ，“删除 ”a[y] 再枚举下一个数 34 } 35 } 36 //递归（深搜）枚举 37 38 int main() 39 { 40 #ifdef ISA_XR 41 freopen(".in","r",stdin); 42 freopen(".out","w",stdout); 43 #endif 44 45 scanf("%d%d",&n,&k); // n 个数 找 k个数 46 for(int i = 1;i <= n;i++) 47 scanf("%d",&a[i]); 48 // 输入数据 49 search(1,0); // 从第一个数开始 50 cout<<ans; //输出 51 52 #ifdef ISA_XR 53 fclose(stdin); 54 fclose(stdout); 55 #endif 56 57 return 0; 58 }
原文：https://www.cnblogs.com/xrisa/p/11507656.html