洛谷 P1036 选数

题目链接：https://www.luogu.com.cn/problem/P1036

这道题的关键在于如何列出所有的选数组合，那么自然想到递归。我们将n个数存入数组num[]中，选数过程可以看作是从下标0～n-1中选择不重复的k个填满k个空位。函数dfs()中sum记录当前已选数的累加和，left记录当前剩余空位数，p指出当前空位可以从num[]中哪一位下标开始选。由于组合是无序的，且不能选择重复的数，所以要遵循从前往后选数的规则，即后一个空位只能选择num[]中下标比前一个空位所选数下标大的数。另一方面，还必须保证后面所有的空位都至少有一个选择，所以当前空位所选数的下标最大只能是n-left。因此p～n-left都是当前可能的选择，遍历所有可能递归调用dfs()进行下一个空位的选择即可。直到left为0，说明已无空位，判定当前的sum是否为素数然后退出。

#include <stdio.h>

int n, k, cnt;
int num[25];

int isPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}

void dfs(int sum, int p, int left)
{
    if (!left)
    {
        if (isPrime(sum))
            cnt++;
        return;
    }
    for (int i = p; i <= n - left; i++)
        dfs(sum + num[i], i + 1, left - 1);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
    dfs(0, 0, k);
    printf("%d\n", cnt);
    return 0;
}