[P1036 [NOIP2002 普及组] 选数]

我的思路是运用递归实现一个树状分支
例如
3 7 12 19
4选3，每个情况为
3-7-12
3-12-19
7-12-19

注意

我们用递归时在传参时要以和的形式传参。
如果先求和再传参就会发生错误.

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
int a[21];
int num = 0;
bool ac(int x) {
	if (x % 2 == 0 && x != 2) {
		return false;
	}
	for (int i = 2; i < x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

void ad(int s, int k, int i, int n, int v ) {
	if (i > k) {
		if (ac(s)) {
			num++;
			return ;
		}
		return ;
	}
	for (int x = 1; x <= n - k + i ; x++) {

		if (v >= x) {
			continue;
		}

		
		ad(s + a[x], k, i + 1, n, x);

	}

}

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int s = 0;
	ad(s, k, 1, n, 0);
	
	cout << num;
	return 0;
}