针对 组合总和 (Combination Sum) 这一题型，我为你准备了符合 NOI 竞赛标准的数据生成器和配套的 SPJ。

由于本题目标值 $T$ 只有 $40$，搜索空间虽然是指数级，但在限制条件下方案数不会多到无法处理，预计单文件大小会远小于 2MB。

一、 数据生成器 (gen.cpp)

该生成器采用 C++14 标准，结合随机数引擎生成 10 个测试点。为了保证 .out 文件的正确性，生成器内置了带剪枝的 DFS 求解器。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <set>

using namespace std;

// 内置求解器用于生成 .out 文件
void solve_dfs(int remain, int start, int n, const vector<int>& a, vector<int>& path, ofstream& fout) {
    if (remain == 0) {
        for (int i = 0; i < (int)path.size(); ++i) {
            fout << path[i] << (i == (int)path.size() - 1 ? "" : " ");
        }
        fout << "\n";
        return;
    }
    for (int i = start; i < n; ++i) {
        if (remain - a[i] < 0) break; // 剪枝
        path.push_back(a[i]);
        solve_dfs(remain - a[i], i, n, a, path, fout);
        path.pop_back();
    }
}

int main() {
    // 测试点参数设计 (n, target)
    int test_n[] = {1, 4, 10, 20, 30, 30, 30, 30, 30, 30};
    int test_t[] = {1, 7, 15, 20, 30, 35, 40, 40, 40, 40};
    
    mt19937 rng(20260105); // 固定种子

    for (int t = 1; t <= 10; ++t) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        
        int n = test_n[t-1];
        int T = test_t[t-1];
        
        // 1. 生成互不相同的 A[i]
        set<int> unique_nums;
        uniform_int_distribution<int> dist(1, 40);
        
        if (t == 2) { // 样例数据
            unique_nums = {2, 3, 6, 7};
            n = 4; T = 7;
        } else {
            while ((int)unique_nums.size() < n) {
                unique_nums.insert(dist(rng));
            }
        }
        
        vector<int> a(unique_nums.begin(), unique_nums.end());
        
        // 2. 写入 .in
        ofstream fin(in_name);
        fin << a.size() << " " << T << "\n";
        for (int i = 0; i < (int)a.size(); ++i) {
            fin << a[i] << (i == (int)a.size() - 1 ? "" : " ");
        }
        fin << "\n";
        fin.close();
        
        // 3. 生成 .out
        ofstream fout(out_name);
        vector<int> path;
        // 求解器需要排序好的数组进行剪枝输出
        sort(a.begin(), a.end());
        solve_dfs(T, 0, a.size(), a, path, fout);
        fout.close();
        
        cout << "Test Case " << t << " generated: n=" << a.size() << ", T=" << T << endl;
    }
    return 0;
}

二、 特判程序 (checker.cpp)

组合总和的输出顺序可能多种多样（组合内顺序、组合间顺序）。该 SPJ 使用 testlib.h 标准，将标准答案读入 set，并逐一核对选手输出的合法性。

#include "testlib.h"
#include <vector>
#include <set>
#include <algorithm>
#include <sstream>

using namespace std;

// 将一行输出转换为排序后的 vector，用于唯一性识别
vector<int> parse_and_sort(string line) {
    stringstream ss(line);
    int val;
    vector<int> res;
    while (ss >> val) res.push_back(val);
    sort(res.begin(), res.end());
    return res;
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    // 1. 读取输入信息
    int n = inf.readInt();
    int T = inf.readInt();
    set<int> candidates;
    for(int i = 0; i < n; ++i) candidates.insert(inf.readInt());

    // 2. 读取标准答案到 set
    set<vector<int>> ans_sets;
    while (!ans.seekEof()) {
        string line = ans.readLine();
        if (line.empty()) continue;
        ans_sets.insert(parse_and_sort(line));
    }

    // 3. 校验选手输出
    set<vector<int>> ouf_sets;
    int line_idx = 0;
    while (!ouf.seekEof()) {
        line_idx++;
        string line = ouf.readLine();
        if (line.find_first_not_of(" \t\r\n") == string::npos) continue; // 跳过纯空白行

        stringstream ss(line);
        vector<int> current_comb;
        long long current_sum = 0;
        int val;
        while (ss >> val) {
            if (candidates.find(val) == candidates.end()) {
                quitf(_wa, "第 %d 行包含不在候选集中的数字: %d", line_idx, val);
            }
            current_comb.push_back(val);
            current_sum += val;
        }

        if (current_sum != T) {
            quitf(_wa, "第 %d 行组合之和为 %lld，不等于目标值 %d", line_idx, current_sum, T);
        }

        sort(current_comb.begin(), current_comb.end());
        if (ouf_sets.count(current_comb)) {
            quitf(_wa, "输出了重复的组合");
        }
        ouf_sets.insert(current_comb);

        if (!ans_sets.count(current_comb)) {
            quitf(_wa, "输出了一个错误的组合（虽然和对但逻辑不符或重复选取规则错误）");
        }
    }

    // 4. 检查是否找全了所有组合
    if (ouf_sets.size() < ans_sets.size()) {
        quitf(_wa, "组合找得不全：期望 %d 个，实际 %d 个", (int)ans_sets.size(), (int)ouf_sets.size());
    }
    
    // 如果 ouf_sets.size() > ans_sets.size() 且每个都在 ans 中，这在逻辑上是不可能的（因为已查重）

    quitf(_ok, "答案正确！找到了全部 %d 个符合条件的组合。", (int)ans_sets.size());
    return 0;
}

三、 测试点设计说明 (区分算法复杂度)

1. #1 & #2 (边界与样例)：$T$ 很小，确保程序能处理最基本逻辑。
2. #3 (小 $T$ 多元素)：测试搜索树的横向宽度。
3. #4 (无解情况)：随机生成的数可能都很大（如 $> 20$），而 $T=20$，测试剪枝是否能快速跳出。
4. #5 & #6 (中等规模)：$T$ 逐渐增大，增加搜索深度。
5. #7 - #10 (极限压力)：$T=40$。
   • 如果选手中包含数字 1，搜索深度会达到 $40$ 层。
   • 如果选手不进行排序剪枝，或者每次都在递归中创建大型对象，会明显慢于标准解法。
   • 这些点能有效区分“带剪枝的 DFS”和“纯暴力遍历”。

四、 复杂度分析与建议

• 生成器效率：由于 $T=40$ 的限制，即使是最慢的合法 DFS 也能在几毫秒内生成答案。
• 空间分析：$30$ 个数凑 $40$，方案数通常在几百到几千个之间。每个方案平均长度约 $5 \sim 10$ 个 int。单文件大小约 $50KB \sim 200KB$，远低于 2MB。
• 异常处理：
  • 爆栈风险：$T=40$ 对应的递归深度极浅（系统栈通常支持数万层），故无需担心爆栈。
  • 除零异常：程序中仅涉及加减法对比和 remain - a[i]，无除法逻辑，安全。

教练提示：在部署 OJ 时，请确保上传了 testlib.h。如果是手动比对，请务必开启忽略行末空格和空行的选项，或者直接使用上述 SPJ 保证评测公平性。

同学，组合总和 (Combination Sum) 是 NOI 搜索专题中的经典题目。它与普通组合问题的核心区别在于：单个元素可以无限次使用。

在赛场上，这类题目通常作为搜索算法性能优化的敲门砖。下面我为你演示从基础回溯到带剪枝的高效搜索的代码实现。

版本一：基础回溯（不带剪枝）

这个版本直接模拟“选与不选”的逻辑。虽然能跑通，但在面对大 $T$（目标值）时，由于没有过滤无效分支，效率较低。

思考过程：

• 核心逻辑：通过 start 索引控制搜索方向。下一层递归仍从 i 开始，从而允许重复选取。
• 时间复杂度：$O(N^{\frac{T}{min\_val}})$。最坏情况下，搜索树的深度由目标值与最小元素的比值决定。
• 空间复杂度：$O(\frac{T}{min\_val})$，主要是递归栈的深度。

#include <iostream>
#include <vector>

using namespace std;

int n, target;
int a[35];
vector<int> path;

// remain: 当前还需要凑出的数值
// start: 为了去重，当前层只能从第 start 个元素开始选
void dfs(int remain, int start) {
    // 递归边界：凑齐了
    if (remain == 0) {
        for (int i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " ");
        }
        cout << "\n";
        return;
    }

    for (int i = start; i < n; ++i) {
        // 如果当前数还没超过剩余目标，可以尝试进入
        if (remain >= a[i]) {
            path.push_back(a[i]);
            // 易错点：这里传 i 而不是 i + 1，表示允许重复使用当前元素
            dfs(remain - a[i], i); 
            path.pop_back(); // 回溯：清理现场
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    if (!(cin >> n >> target)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    dfs(target, 0);

    return 0;
}

版本二：最优复杂度——排序 + 结构化剪枝 (NOI 推荐)

这是在竞赛中最常用的写法。通过预先排序，我们可以利用单调性实现“一断百断”的剪枝。

思考过程：

• 剪枝逻辑：如果数组是有序的，且当前元素 $A[i]$ 已经大于剩余目标值 $remain$，那么 $A[i]$ 之后的所有元素（都更大）也一定不满足条件。
• 优化点：直接 break 掉当前循环，不再进行无意义的后续递归。

#include <iostream>
#include <vector>
#include <algorithm> // 必须引入排序

using namespace std;

int n, target;
int a[35];
vector<int> path;

void dfs(int remain, int start) {
    if (remain == 0) {
        for (int i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " ");
        }
        cout << "\n";
        return;
    }

    for (int i = start; i < n; ++i) {
        // 关键剪枝点：
        // 如果当前数值已经大于剩余所需目标，后续更大的数无需再看
        if (remain - a[i] < 0) break; 

        path.push_back(a[i]);
        // 传递 i 以允许无限重复选取
        dfs(remain - a[i], i);
        path.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> target)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 核心优化：为了剪枝，必须先升序排序
    sort(a, a + n);

    dfs(target, 0);

    return 0;
}

复杂度分析与优化建议总结

1. 时间复杂度分析思考

• 搜索树规模：组合总和的解集数量是指数级的。
• 剪枝效果：排序后的 break 剪枝在 $T$ 较大而 $A[i]$ 分布广泛时，能减少 80% 以上的无效搜索。
• 总体：$O(S)$，其中 $S$ 为所有可行解的长度之和。对于 $T=40$ 的限制，搜索次数在万级以内，1.0s 时限内极度安全。

2. 空间复杂度分析

• 路径存储：$O(T)$，最极端情况是 $T$ 个 1。
• 递归栈：$O(T)$。
• 内存建议：本题不建议使用 vector<vector<int>> 存储所有结果后再输出，因为如果解的数量巨大，可能会触发 MLE。在 NOI 中，“边搜边输出” 是处理此类题目的黄金准则。

3. 性能优化建议

1. I/O 速度：本题结果集可能很大，输出行数较多。务必使用 \n 而非 endl。
2. 快读快写：如果数据量进一步加大到 $N=1000$ 级别（虽然本题不是），建议使用 getchar() 实现的快读。
3. 状态设计：如果本题只要求“输出满足条件的方案数”而不是具体方案，那么请立即抛弃 DFS，改用完全背包动态规划，复杂度将从指数级降至 $O(n \cdot T)$。

读题关键词总结 (NOIP/NOI 考场提示)

读这类题时，这几个关键词决定了你的代码框架：

1. “无限制重复选取” $\rightarrow$ 递归时传 i 而不是 i + 1。
2. “唯一组合” $\rightarrow$ 通过 start 索引控制枚举顺序，禁止向后选。
3. “无重复元素” $\rightarrow$ 免去了在同一层判断 a[i] == a[i-1] 的去重逻辑。
4. “正整数” $\rightarrow$ 保证了 remain 会单调减小，从而使 remain < 0 成为合法的剪枝条件。

教练点评： 这道题是“回溯法”进阶的必考题。很多同学会卡在“如何去重”上，记住：只要控制好枚举的起始索引，不需要用 set 去重也能保证唯一。 版本二中的剪枝公式 if (remain - a[i] < 0) break; 是这道题的提分核心，请务必熟练掌握！加油！