广州C++信奥老师解一本通题 1919：【02NOIP普及组】选数

【题目描述】

已知nn个整数x1,x2,……xn 以及一个整数K(K＜n)。从n个整数中任选K个整数相加,可分别 得到一系列的和。例如当n=4, k=3 4个整数分别为3,7,12,19 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)

第二行为n个数

x1x2……xn(1≤xi≤5000000),各数之间用一个空格隔开)

【输出】

一个整数(满足条件的种数)。

【输入样例】

4 3 
3 7 12 19

【输出样例】

1

此题跟1317：【例5.2】组合的输出 解法类似

#include <bits/stdc++.h>
using namespace std;
long long path[21],a[21];  //path存放组合的元素的数字 
int n,k,ans=0;  
bool isPrime(long long n)
{if(n<=1)return false;for(int i = 2; i <= sqrt(n);i++)if(n % i == 0)return false;return true;
}
void dfs(int start,int cnt)
{if(cnt>k){long long sum=0; for(int i=1;i<=k;i++)sum+=path[i];if( isPrime(sum) )ans++;return;}for(int i=start;i<=n;i++) //递归尝试数组元素下标 1，2，3，4等 {path[cnt]=a[i];dfs(i+1,cnt+1);}
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];memset(path,0,sizeof(path));dfs(1,1);cout<<ans;return 0;
}