题解：P1036 [NOIP 2002 普及组] 选数
zhangzirui66
·
·
题解
闲话
本文同步发布在 cnblogs。
代码复杂度约为 $O(2^n\sqrt{2^n})$，实际完全跑不满：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, k, a[25], use[25], ans;
bool prime(int x){// 基本的判断素数
if(x < 2) return 0;
for(int i = 2; i * i <= x; i ++){
if(x % i == 0) return 0;
}
return 1;
}
void dfs(int dep, int sum){ // dep：搜了几个数，sum：当前总和
if(dep == k + 1){
ans += (int)(prime(sum));// 一个简写，因人而异
return;
}
for(int i = use[dep - 1] + 1; i <= n; i ++){
use[dep] = i;// use：上次选的是第几个，避免重复
dfs(dep + 1, sum + a[i]);
}
}
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
dfs(1, 0);
cout << ans;
return 0;
}
```