看了题解，竟然有大佬枚举出来了，最多用了10个for，tql%%%
就想着用深搜了，第一发wa了，重复计算了，后来改过来了
题目
已知 nn 个整数 x_1,x_2,…,x_nx1?,x2?,…,xn?，以及11个整数kk(k<nk<n)。从nn个整数中任选kk个整数相加，可分别得到一系列的和。例如当n=4,k=3n=4,k=3,44个整数分别为3,7,12,193,7,12,19时，可得全部的组合与它们的和为：
3+7+12=223+7+12=22
3+7+19=293+7+19=29
7+12+19=387+12+19=38
3+12+19=343+12+19=34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=293+7+19=29。
输入格式：
键盘输入，格式为：
n , k ( 1 ≤ n ≤ 20 , k < n )
x1 , x2 , … , xn ( 1 ≤ xi ?≤ 5000000)
输出格式：
屏幕输出，格式为： 1个整数（满足条件的种数）。
1
题解
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstdio> 4 #include <cmath> 5 6 using namespace std; 7 void dfs(int num); //深搜 8 bool check(int num); //判断这个数在前面出现过没有 9 bool judge(int num); //判断合法的和是不是素数 10 bool fun(int num); //避免重复计算，保证后面的数下标比前面的数下标大 11 int n, k, ans, a[30], b[30]; 12 13 int main() 14 { 15 cin >> n >> k; 16 for(int i = 0; i < n; i ++ ) scanf("%d",&a[i]); 17 18 dfs(0); 19 printf("%d",ans); 20 return 0; 21 } 22 23 void dfs(int num) 24 { 25 if(num >= k) 26 { 27 if(fun(num)) 28 { 29 int temp = 0; 30 for(int i = 0; i < k; i ++ ) 31 temp += a[b[i]]; 32 //printf("%d\n",temp); 33 if(judge(temp)) ans ++ ; 34 return; 35 } else return; 36 } 37 for(int i = 0; i < n; i ++ ) 38 { 39 b[num] = i; 40 if(check(num)) 41 dfs(num + 1); 42 } 43 } 44 45 bool check(int num) 46 { 47 for(int i = 0; i < num; i ++ ) 48 if(b[i] == b[num]) return 0; 49 return 1; 50 } 51 52 bool judge(int num) 53 { 54 for(int i = 2; i <= sqrt(num); i ++ ) 55 if(num % i == 0) return 0; 56 return 1; 57 } 58 59 bool fun(int num) 60 { 61 for(int i = 0; i < num - 1; i ++ ) 62 if(b[i] > b[i + 1]) return 0; 63 return 1; 64 }
原文：https://www.cnblogs.com/chuyds/p/10976818.html