广州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;
}

​