hello,大家好(普通到再普通不过的招呼),只是我的第一篇帖子，请大家多多点赞.(可以关注我吗awa)

话不多说，上正题~

关注链接:戳此关注~

每周一题之选数

选数

题目描述

已知 $n$ 个整数，从中选出 $k$ 个数，把选出的 $k$ 个数相加得到和。求一共有多少种选法，使得选出数字的和是质数。

注意：选数只看集合，顺序无关。例如从 $\{1,2,3\}$ 选 $2$ 和 $3$，与选 $3$ 和 $2$ 算作同一种方案。

输入格式

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_i$。

输出格式

输出一个整数，表示满足条件的方案总数。

数据范围

$1 \le n \le 20$，$1 \le k \le n$，$1 \le a_i \le 5\times10^6$

样例输入 1

样例解释：

• $3+7+11=21$，不是质数
• $3+7+19=29$，是质数
• $3+11+19=33$，不是质数
• $7+11+19=37$，是质数
  合计 $2$ 种方案。

样例输入 2

样例解释：

• $2+3=5$，质数
• $2+4=6$，非质数
• $3+4=7$，质数
  合计 $2$ 种方案。

考点

回溯（深度优先搜索）、组合选取、素数判定，NOIP普及组真题难度。

提示

1. 做组合枚举，下标只能向后选取，避免重复统计。
2. 总和最大可达 $10^8$，无法使用埃氏筛，使用试除法判断素数。
3. 递归边界：选够 $k$ 个数时，判断和是否为质数，统计答案。

题目思路

题意概括

从 $n$ 个数字里选恰好 $k$ 个（组合，不考虑顺序），统计有多少组，它们的总和是质数。

组合：选第0个、第1个 和 选第1个、第0个 是同一种，不能重复计数。

核心思路：DFS回溯枚举组合

DFS参数

• pos：当前处理到数组的下标，只能往后选，不回头，避免重复组合
• cnt：已经选了多少个数
• sum：已经选的数的累加和

递归逻辑

1. 边界1：已经选够 k 个数
   判断 sum 是不是质数，如果是，答案 ans++，直接返回。
2. 边界2：pos走到数组末尾（全部遍历完）
   直接返回，不能再选数。
3. 两种分支（每个数两种选择：选 / 不选）
   • 不选当前 a[pos]：直接递归下一个位置 dfs(pos+1, cnt, sum)
   • 选当前 a[pos]：递归 dfs(pos+1, cnt+1, sum+a[pos])

为什么pos+1：选过的下标不再回头，保证只会生成组合，不会生成排列。

素数判断要点

总和最大：$20 \times 5\times10^6=10^8$，数组开不下筛法，只能用试除法。

• 小于等于1：一定不是质数
• 从2循环到 $\sqrt{s}$，如果能整除，不是质数。

注意：sqrt() 返回double，循环条件建议写成 i*i <= s 避免浮点精度坑。

dfs补全片段

void dfs(int pos,int cnt,int sum){
    if(cnt == k){
        if(isPrime(sum)) ans++;
        return;
    }
    if(pos >= n) return;
    // 不选
    dfs(pos+1, cnt, sum);
    // 选
    dfs(pos+1, cnt+1, sum + a[pos]);
}

易错点

1. 递归下标错误，造成重复选数、重复统计方案

错误写法：dfs(pos, cnt, sum)
正确写法：dfs(pos + 1, cnt, sum)
说明：必须 pos+1，只能向后遍历，不能停留在当前下标，否则会重复选取同一个数字，把组合变成排列，答案偏大。

2. 递归边界判断顺序颠倒

错误：先判断 pos >= n，再判断 cnt == k
正确：先判断 cnt == k，再判断 pos >= n
说明：如果走到数组末尾时刚好选够k个数，先判断pos越界会直接return，漏掉本应统计的方案。

3. 素数判断使用 sqrt() 带来浮点数精度问题

错误：for(int i = 2; i <= sqrt(s); i++)
正确：for(int i = 2; i * i <= s; i++)
说明：sqrt返回double，大数会存在精度误差，i*i <= s 全部整数运算更安全。

4. 素数函数缺少 s <= 1 的判断

如果总和等于1，1不是质数，不做判断会错误算成质数。

5. sum整型溢出隐患
   本题数据范围下 int 够用；如果题目数据放大，sum 需要改为 long long，否则总和溢出变成负数，素数判断全部出错。

6. 混淆组合与排列
   不要往回访问前面的下标，一旦允许 pos 往前，就会出现 {3,7} 和 {7,3} 两套重复方案，ans结果翻倍。

7. 全局变量 ans 忘记重置
   多组测试数据场景下，ans 要清零；本题只有单组输入，不会暴露这个bug。

时间复杂度

总共有 $C_{n}^{k}$ 种组合需要枚举。
本题 $n \le 20$，最坏情况为 $C_{20}^{10}=184756$，组合数量不大，暴力DFS可以轻松通过。

每得到一组合法组合后，需要执行素数试除法。试除法时间复杂度为 $O(\sqrt{S})$，$S$ 为选出数字的总和，最大为 $10^8$，$\sqrt{S}$ 最大约 $10^4$。

整体复杂度：$O\left(C_{n}^{k} \cdot \sqrt{S}\right)$。

AC完整代码（带详细注释）

#include <iostream>
#include <cmath>
using namespace std;

int n;          // 数字总个数
int k;          // 需要选出的数字数量
int a[25];      // 存储输入的数字，n最大20，数组开25足够
int ans = 0;    // 记录合法方案总数

/**
 * 判断一个数是否为质数
 * 待判断的和
 * 是质数返回true，否则false
 */
bool isPrime(int s){
    // 小于等于1一定不是质数
    if(s <= 1)
        return false;
    // i*i <= s 代替sqrt，避免浮点运算精度问题
    for(int i = 2; i * i <= s; i++){
        // 可以整除，说明存在因数，不是质数
        if(s % i == 0)
            return false;
    }
    return true;
}

/**
 *DFS回溯搜索组合方案
 * pos 当前遍历到数组的下标
 * cnt 已经选了多少个数字
 * sum 当前已经选数字的累加和
 */
void dfs(int pos, int cnt, int sum){
    // 递归边界：已经选够k个数字
    if(cnt == k){
        // 和为质数则方案数+1
        if(isPrime(sum))
            ans++;
        return;
    }
    // 递归边界：下标走到数组末尾，没有数字可选
    if(pos >= n)
        return;

    // 分支1：不选当前a[pos]，直接处理下一个下标
    dfs(pos + 1, cnt, sum);

    // 分支2：选当前a[pos]，已选数量+1，总和累加
    dfs(pos + 1, cnt + 1, sum + a[pos]);
}

int main(){
    // 读入n和k
    cin >> n >> k;
    // 读取n个整数存入数组
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    // 从下标0开始，已选0个，总和0，启动DFS
    dfs(0, 0, 0);
    // 输出答案
    cout << ans << endl;
    return 0;
}

总结

本题是NOIP普及组经典搜索题，核心考察DFS回溯求组合与素数判定。

1. 算法思想
   使用深度优先搜索枚举所有选k个数的组合，每个数字有选、不选两种分支；通过pos+1只向后遍历下标，避免生成排列，保证只枚举组合。每当选够k个数，就判断总和是否为质数，统计合法方案。

2. 核心函数作用

• isPrime：试除法判断质数，优先使用i*i <= s避免浮点精度问题，记得处理小于等于1的特殊情况。
• dfs：回溯主体，三个参数分别记录当前下标、已选数量、累加和，两个递归边界分别处理选满k个数、遍历完数组。

3. 复杂度
   时间复杂度 $O(C_{n}^{k} \cdot \sqrt S)$，$n\le20$，组合数量不大，暴力搜索完全可以通过。

4. 高频坑点

• dfs递归一定要pos+1，不能停留在原下标；
• 边界顺序：优先判断选够k个，再判断下标越界；
• 素数判断注意1不是质数，规避sqrt浮点数误差；
• 数据规模变大时sum要改用long long防止溢出。

5. 拓展
   如果n继续增大，暴力DFS会超时，可以使用动态规划优化；本题数据范围小，回溯是最简单直观的解法。

最后感谢您的阅读，动动你的金手指给个赞吧~