[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;
}