P1036 [NOIP2002 普及组] 选数

思路：也算典型的dfs，题目就是要求从n个数中选择k个数，计算这k个数的和，看这个和是否是素数。我们知道在dfs时相当于是进行全排列，而结果要求的是组合后和的情况。根据排列和组合的关系，他们之间差K！倍，所以需要在dfs求得个数cnt后除以k！。

题目：

AC代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;

//输入n，k，从n个数中选k个数
int n,k;
int a[25];//记录n个数
int path[25];//记录选择的k个数
bool vis[25];//记录n个数的状态
int cnt = 0;
int ss=1;

void dfs(int u){
	if(u == k)//如果有k个数了
	{
		int sum=0;
		for(int i=0;i<k;i++){			
			sum+=path[i];
		}
	//	printf("summ%d\n",sum);
		//1不是素数			
		for(int i=2;i<sqrt(sum);i++){
			if(sum % i == 0){
				return ;
			}
		}
		cnt++;
		return;
	} 
	//要确保每种搭配方式只出现一次！！！！
	 
	for(int i=0;i<n;i++){
		if(!vis[i])//如果这个数没用
		{
			vis[i] = true;
			path[u] = a[i];
			dfs(u+1);
			vis[i] = false;
			path[u] = 0;
		} 
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}	

	for(int i=1;i<=k;i++){
		ss *= i;
	//	cout<<ss<<endl; 
	} 
	
	dfs(0);
	printf("%d",cnt/ss);
	return 0;
} 

结果：