题解 | #[NOIP2002]选数#

#include <stdio.h> #include <math.h>

// 判断素数函数 int isPrime(int num) { if (num <= 1) return 0; if (num == 2) return 1; if (num % 2 == 0) return 0;

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

}

int n, k; int numbers[20]; int count = 0;

// DFS函数：从n个数中选择k个数 void dfs(int start, // 当前搜索起始位置 int selected, // 已选择的数字个数 int sum) { // 当前已选数字的和

// 剪枝：如果剩余数字不够选择，直接返回
// 例如：还需要选2个数字，但只剩1个数字可选
if (n - start < k - selected) {
    return;
}

// 终止条件：已经选择了k个数字
if (selected == k) {
    // 检查这k个数字的和是否为素数
    if (isPrime(sum)) {
        count++; // 素数组合计数加1
    }
    return; // 返回上一层
}

// 从start位置开始，尝试选择每个可能的数字
for (int i = start; i < n; i++) {
    // 选择numbers[i]，然后递归深入
    // i+1: 下一个搜索位置，避免重复选择
    // selected+1: 已选数字个数加1
    // sum + numbers[i]: 更新当前和
    dfs(i + 1, selected + 1, sum + numbers[i]);
    
    // 注意：这里不需要显式撤销选择，因为：
    // 1. sum和selected是通过值传递的，不是引用
    // 2. 每次递归调用都有自己独立的状态副本
    // 3. 递归返回后，自动回到当前状态
}

}

int main() { scanf("%d %d", &n, &k);

for (int i = 0; i < n; i++) {
    scanf("%d", &numbers[i]);
}

// 从第0个位置开始，已选0个数字，当前和为0
dfs(0, 0, 0);

// 输出结果
printf("%d", count);

return 0;

}