PP4904 带重复元素的K数之和计数（基础）

解题思路

第一步，明确要求。 从 n 个数里任选 k 个相加，统计"不同的和"一共有几种。虽然元素可能有重复，但相同的和只算一次。例如 1、2、2 中选 2 个，和只有 3 和 4 两种，答案是 2。

第二步，设计搜索。 n 最多 20，组合数有限，可以深度优先搜索。用 dfs(idx,num) 表示"现在考虑第 idx 个数，已经选了 num 个"。

第三步，两种分支。 对每个数都有两种选择：不选它（dfs(idx+1,num)）或选它（sum 加上它再递归，回溯时减掉）。当 num 正好等于 k 时，说明凑出了一种和，用 vis 数组标记这个和是否出现过，第一次出现就把计数 cnt 加一。

第四步，剪枝优化。 如果剩下的数已经不够选满 k 个（n-idx < k-num），就直接返回，避免无效搜索。

边界情况。 所有数的和最多 20×50=1000，所以 vis 数组开 1005 就够。回溯时一定要把 sum 减回来，否则会出错。

参考代码

// P4904 带重复元素的K数之和计数 深搜：选 k 个数统计不同和
#include <iostream>
using namespace std;
int x[25]; // 给定的整数
int n, k, sum, cnt; // n 个数, 选 k 个, sum 当前和, cnt 不同和的个数
bool vis[1005]; // 标记某种和是否出现过
void dfs(int idx, int num) { // idx 当前下标, num 已选个数
    if (num == k) {
        if (!vis[sum]) { vis[sum] = true; cnt++; } // 出现新和
        return;
    }
    if (idx >= n || n - idx < k - num) return; // 剩下的数不够选了
    dfs(idx + 1, num); // 不选 x[idx]
    sum += x[idx]; // 选 x[idx]
    dfs(idx + 1, num + 1);
    sum -= x[idx];
}
int main() {
    int i;
    cin >> n >> k;
    for (i = 0; i < n; i++) cin >> x[i];
    dfs(0, 0);
    cout << cnt << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(C(n,k))，即组合数级别的搜索；由于 n≤20，最坏情况也可接受。空间复杂度 O(n) 用于递归栈。