【题目描述】

$n=4$, $=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个数$x_1{x}_2\dots \dots x_n(1\le x_i\le 5000000)$,各数之间用一个空格隔开)

【输出描述】

        一个整数（满足所有条件的种数）

【样例输入】

4 3 
3 7 12 19

【样例输出】

1

【题目分析】

• 用到了判断素数

• 简单的排列是不行的，比如3 7 12 和3 12 7 是两种不同的排列，但是加起来的结论是一样的，所以要进行简单改变

【解法一：利用组合数公式】

如果我们用的DFS把所有可能的排列情况求出来，那么肯定是重复的，既然这样，我们就用组合数公式，可以看出，组合数公式就是排序数除以m的阶乘。那么题目来说就比较简单了。

#include <bits/stdc++.h>
using namespace std;
long long n,k,sum,cnt,times,flag,a[21],vis[21];
//检测质数 
void check(long long sum) {
	flag=0;//clear
	if(sum!=2) {
		for(int i=2; i*i<=sum; i++) {
			if(sum%i==0) {
				flag=1;
				break;
			}
		}
	}
	if(sum==2) flag=0;
	if(flag==0) cnt++;
}
void dfs(long long depth) {
	if(depth==k+1) {
		check(sum);//判断是否是质数 
		return;
	}
	for(int i=1; i<=n; i++) {
		if(vis[i]!=1) {
			vis[i]=1;  //标记被使用过了 
			sum+=a[i];  //把使用过的数加起来 
			dfs(depth+1); //深搜下一个 
			sum-=a[i];
			vis[i]=0;  //回溯一步 
		}
	}
}
int main() {
	cin>>n>>k;//读入n和k 
	for(int i=1; i<=n; i++)
		cin>>a[i];
	dfs(1);
	times=1;  //阶乘
	for(int i=1; i<=k; i++) 
		times*=i;
	cout<<cnt/times<<endl;
	return 0;
}

【解法二：利用单调性筛选】

我们不能直接用DFS的方法，是因为有重复的数据，只要我们保证我们产生的数据没有重复的，就OK了。

比如，我们4选3。比较好的写法应该是

1 2 3 
1 2 4
1 3 4
2 3 4

那么我们只要保证在全排列的时候，后面的数比前面的大就能作出组合数了。