📚 算法笔记：P1036 [NOIP 2002 普及组] 选数

1. 题目描述

[P1036 NOIP 2002 普及组] 选数 - 洛谷

从 $n$ 个整数中任选 $k$ 个数相加，统计有多少种选法的和为质数。

• 数据范围：$n\le 20,k<n$，每个整数 $<5\times 10^6$。

2. 核心代码 (C++ AC版本)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[25];        // 存储输入的 n 个数
int N, K;
ll ans = 0;      // 计数器：符合条件的质数和个数

// 质数判定：O(sqrt(sum))
bool is_prime(int n) 
{
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) 
    { 
        if (n % i == 0) return false;
    }
    return true;
}

// DFS 组合模型
// position: 当前选到了第几个数
// sum:      当前已选数字的累加和
// start:    搜索起点，保证下标单调递增
void dfs(int position, ll sum, int start)
{
    // 1. 递归出口：选够了 K 个数
    if(position > K)
    {
        if(is_prime(sum)) ans++;
        return; 
    }
    
    // 2. 组合模型核心：从 start 开始往后选，不回头
    for(int i = start; i <= N; i++)
    {
        // 隐式回溯：sum + a[i] 作为参数传递，无需手动撤销
        dfs(position + 1, sum + a[i], i + 1);
    }
}

void solve()
{
    if(!(cin >> N >> K)) return;
    for (int i = 1; i <= N; i++) cin >> a[i];
    
    ans = 0;
    dfs(1, 0, 1);
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int _ = 1;
    while(_--) solve();
    return 0;
}

3. 核心考点与注意事项

• 组合模型 (Combination)：与全排列不同，组合不计较顺序。通过引入 start 参数，强制让选取的下标单调递增（$i\to i+1$），从而物理隔绝了重复排列（如选了 $1,2$ 就不会再选 $2,1$）。
• 隐式回溯：在 dfs(position + 1, sum + a[i], i + 1) 中，sum + a[i] 的结果直接传给下一层。当递归返回时，本层的 sum 值并没有改变，因此不需要像 used 数组那样手动执行 sum -= a[i]。
• 质数优化：使用 i * i <= n 进行判定，时间复杂度为 $O(\sqrt{N})$，是应对高频调用的标准写法。