组合 - [NOIP2002 热门组] 选项

[NOIP2002 普及组] 选数

题目描述

已知 \(n\) 个整数 \(x_1,x_2,\cdots,x_n\)，以及 \(1\) 个整数 \(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 \le n \le 20\)，\(k<n\)）。

第二行 \(n\) 个整数，分别为 \(x_1,x_2,\cdots,x_n\)（\(1 \le x_i \le 5\times 10^6\)）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

思路

从题目可以看出，这是一道组合题。从n个数中选择k个数且k个数之和是素数的组合种类。
1）组合，众所周知123和321是一种，因此搜索中的形参要有开始搜索位置，下一次搜索时从下一个位置开始搜索就可以了，比如1，2，3中选俩的组合

12
13
23

这里一开始的搜索位置是1，然后从2开始就避免了像21，31这种情况。

2）那什么时候递归结束呢？当选择了三个数字后就递归结束对所选数字的和是否是素数进行判断，如果是素数ans++因此搜索形参中要有已选数字数量这一参数

3）递归结束时我们就要对所选数字之和进行判断了，所以形参中有已选数字之和，每选一个数字sum+所选数字值。

代码

#include<iostream>
using namespace std;
int a[30];
int n, k;
long long ans = 0;
bool isprime(int x) {
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)return false;
	return true;
}
void dfs(int k, int start, int sum) {
	if (k == 0) {
		if (isprime(sum))ans++;
		return;
	}
	for (int i = start; i < n; i++)
		dfs(k - 1, i + 1, sum + a[i]);
	return;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	dfs(k, 0, 0);
	cout << ans << endl;
}

原文地址：https://www.cnblogs.com/wxy214/p/16353497.html