【洛谷】P1036 [NOIP2002 普及组] 选数

题目描述：

P1036 [NOIP2002 普及组] 选数

思维点：

逐个搜素添加
注意临界条件
要先判定能否添加
再判定下一步添加能否进行

题解

#include <iostream>
using namespace std;

int x[20];
int n, k, ans;

bool is_prime(int n) {
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)
			return false;
	return true;
}

void dfs(int i, int now, int sum) { //i为下一个等待添加的元素的编号， now为现在已要的个数， sum为已要数字的和
	if (now == k) {
		if(is_prime(sum))
			ans++;
		return;
	}
	if (i >= n) return;//注意两个if的先后顺序不能反，这个if是判定能不能接着往下搜索的 
	dfs(i + 1, now, sum);
	dfs(i + 1, now + 1, sum + x[i]);
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> x[i];
		
	dfs(0, 0, 0);
	
	cout << ans;
	return 0;
}