很常见的一个搜索顺序，维护了一个单调性(start)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int n, k;
int a[N];
int res;

bool is_prime(int x)
{
    if (x < 2)return false;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }

    return true;
}

void dfs(int u, int x, int start)
{
    if (u == k)
    {
        if (is_prime(x))
        {
            res++;
        }
        return;
    }

    for (int i = start; i < n; i++)
    {
        dfs(u + 1, x + a[i], i + 1);
    }

    return;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    dfs(0, 0, 0);

    cout << res << endl;

    return 0;
}