选数

题目描述
已知 n 个整数 x1,x2,…,xn，以及一个整数 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）

输出
一个整数（满足条件的种数）。

输入样例
4 3
3 7 12 19

输出样例
1

题意分析
这题要求，n数中取k个数出来相加，判断和是否为素数，并进行累加

试题难度
★★☆☆☆

解题思路
这题可以采用记忆化搜索，省去不必要的循环，代码如下：

void dfs(int dep,int e)
{
	if(dep==m) {if(d[a]==0) {d[a]=1;p[a]=ss(a);}//判断是否出现过这个数if(p[a])l++;return;}//累加并返回
	for(int i=e;i<=n;i++)//搜索
	 if(c[i]==0)//判断是否用过
	 {
	 	c[i]=1;
	 	a+=b[i];//相加
		dfs(dep+1,i+1);
	 	a-=b[i];//回溯
	 	c[i]=0;
	 }
}

将任意k个数进行相加和素数判断，为了防止超时，可以简化，最后输出素数总和

解题反思
需要判断这个数是否已经进行累加，否则会重复进行累加

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,b[25],a,l,c[25],d[100000005],p[100000005];//用来存数，记忆化搜索
int ss(int n)//素数判断
{
	if(n==0||n==1) return 0;
	for(int i=2;i<=sqrt(n);i++)
	 if(n%i==0) return 0;
	return 1; 
}
void dfs(int dep,int e)
{
	if(dep==m) {if(d[a]==0) {d[a]=1;p[a]=ss(a);}if(p[a])l++;return;}//累加并返回
	for(int i=e;i<=n;i++)//搜索
	 if(c[i]==0)//判断是否用过
	 {
	 	c[i]=1;
	 	a+=b[i];//相加
		dfs(dep+1,i+1);
	 	a-=b[i];//回溯
	 	c[i]=0;
	 }
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 cin>>b[i];  
	sort(b+1,b+n+1);//可以不用
	dfs(0,1);
	cout<<l; 
}

各位大佬，能不能给本蒟蒻点个赞，谢谢了，我初入CSDN，还望大家多多关照