广搜写法

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[25];
struct State
{
    // 前 a 个数，选了 b 个，和为 sum
    int a, b, sum;
};
queue<State> q;
bool isP(int x)
{
    if (x < 2)
        return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    q.push((State){0, 0, 0});
    while (!q.empty())
    {
        State now = q.front();
        q.pop();
        if (now.b == k)
        {
            if (isP(now.sum))
                ans++;
            continue;
        }
        if (now.a == n)
            continue;
        // 考虑第 now.a+1 个数选不选
        q.push((State){now.a + 1, now.b, now.sum});
        q.push((State){now.a + 1, now.b + 1, now.sum + a[now.a + 1]});
    }
    cout << ans;
    return 0;
}