50| 选数

#include <bits/stdc++.h> using namespace std; int n, k, ans, sum; // ans = 最终答案 const int N = 23; int a[N]; bool st[N]; bool isprime(int x) { if (x <= 1) return false; for (int i = 2; i <= sqrt(x); i++) if (x % i == 0) return false; return true; } void dfs(int id, int cnt) { // cnt = 当前选了几个数 // 终止条件：选够 k 个 if (cnt == k) { if (isprime(sum)) ans++; return; } for (int i = id; i <= n; i++) { if (st[i]) continue; st[i] = true; sum += a[i]; dfs(i + 1, cnt + 1); sum -= a[i]; st[i] = false; } } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; dfs(1, 0); // 从第1个数开始，已选0个 cout << ans << endl; return 0; }