你好，同学。欢迎进入 NOI 专题训练。

今天我们要攻克的是组合搜索中的高频考点——处理重复元素的组合问题。这道题（对应力扣 LCR 082 / 40 题）在 NOI 考场上属于搜索算法的必备基本功，重点考察对搜索空间去重的理解。

一、 题目描述 (NOI 风格)

题目名称：含有重复元素集合的组合 (Combination Sum II) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个包含 $n$ 个正整数的序列 $A$，其中可能包含重复的数字。再给定一个目标总和 $T$。 请设计一个算法，找出 $A$ 中所有可以使数字和为 $T$ 的唯一组合。

注意：

1. 序列 $A$ 中的每个数字在每个组合中只能使用一次。
2. 解集不能包含重复的组合（例如 {1, 2, 5} 与 {2, 1, 5} 视为同一个组合，只能输出一次）。
3. 你可以按任意顺序输出组合。

【输入格式】 输入共两行。 第一行包含两个整数 $n$ 和 $T$，分别表示序列长度和目标总和。 第二行包含 $n$ 个以空格隔开的正整数，表示序列 $A$。

【输出格式】 输出若干行，每行表示一个符合条件的组合。元素之间用空格隔开。如果不存在满足条件的组合，则不输出。

【样例输入】

7 8
10 1 2 7 6 1 5

【样例输出】

1 1 6
1 2 5
1 7
2 6

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 100$，$1 \le A[i] \le 50$，$1 \le T \le 30$。

二、 预备知识点

1. 带权回溯算法 (Backtracking)：搜索符合特定和的状态空间。
2. 树层剪枝 (Tree-level Pruning)：这是解决“重复元素”问题的灵魂，用于在搜索时跳过产生相同结果的分支。
3. 排序 (Sorting)：通过排序让相同的数字相邻，是去重的前置条件。

三、 启发式思路引导

请拿出你的草稿纸，我们尝试推导出不重不漏的搜索策略：

1. 为什么会产生重复组合？

假设输入是 {1, 1, 2}，目标和 $T=2$。 如果你在第一层选了“第一个 1”，后续可以选出 {1, 1}； 如果你在第一层选了“第二个 1”，后续也可以选出 {1, 1}。 这就会导致答案集中出现两个一样的 {1, 1}。

2. “树层去重”逻辑（核心重点）

为了避免上述情况，我们规定：在搜索树的同一层，如果当前的数字和前一个选过的数字相同，则这个分支不再重复开启。

• 前提：数组必须先排序。
• 判断条件：if (i > start && A[i] == A[i-1]) continue;
  • i > start 表示在当前这一层递归的循环中，我们选取的不是第一个元素。
  • A[i] == A[i-1] 表示这个数字在当前层已经尝试过了。

3. 复杂度分析思考

• 时间复杂度：虽然组合问题的上限是 $O(2^n)$，但由于 $T$ 只有 30，且 $A[i]$ 是正整数，搜索深度受到极大的限制。加上排序后的剪枝，实际运行效率远高于理论上限。
• 空间复杂度：$O(n)$，主要是递归深度和路径存储。

四、 算法流程图 (C++14 伪代码表示)

请注意观察递归调用时索引的变化，以及去重的关键节点。

graph TD
    Start(开始) --> SortAction(对数组 A 排序)
    SortAction --> Init(初始化 path 数组)
    Init --> CallDFS("DFS(目标值 T, 搜索起点 0)")

    subgraph DFS_Process [递归函数 DFS-remain-start]
    Check{remain 等于 0 ?}
    Check -- Yes --> Save(保存当前 path 并返回)
    Check -- No --> LoopInit("循环 i 从 start 到 n-1")
    
    LoopInit --> Prune1{"A-i 大于 remain ?"}
    Prune1 -- Yes --> Break("剪枝: 后面数字更大, 直接退出循环")
    
    Prune1 -- No --> Prune2{"i 大于 start 且 A-i 等于 A-i减1 ?"}
    Prune2 -- Yes --> NextI("去重: skip 当前数字进入下一次循环")
    
    Prune2 -- No --> Action("将 A-i 放入 path")
    Action --> Recur("递归 DFS(remain - A-i, i + 1)")
    Recur --> Pop("回溯: path.pop_back")
    Pop --> NextI
    end

    Break --> Return((返回上一层))
    Save --> Return
    NextI --> LoopEnd{循环结束?}
    LoopEnd -- Yes --> Return

五、 读题理解关键词

在 NOI 考场上看到此类题，请锁定以下信号：

1. “包含重复数字”：100% 需要先 sort，并在 for 循环内进行相邻元素比对去重。
2. “每个数字只能用一次”：意味着递归下一层时，start 参数应传入 i + 1（区别于 Combination Sum I 的传入 i）。
3. “唯一组合”：再次提醒你必须去重，不能仅仅靠 DFS 跑全集。
4. “正整数”且“目标和”：暗示如果当前数值已经超过了剩余目标，可以直接 break 掉当前 for 循环（强力剪枝）。

六、 优化建议 (NOI 竞赛视角)

1. I/O 优化：如果输出方案数极多，使用 "\n" 代替 std::endl。
2. 搜索常数：在 DFS 传参时，尽量传 remain 的递减值，而不是维护一个 current_sum 去和 target 比较，这样可以少一个参数或少一次加法。
3. 数组范围：注意 $n=100$，虽然本题 $T$ 很小，但如果题目以后变动，$O(2^{100})$ 必然超时，此时要考虑是否需要动态规划（DP）转换。

教练寄语： “树枝去重”（每个元素用一次）和“树层去重”（相同元素不重选）是搜索算法中最精妙的双重逻辑。请务必在草稿纸上模拟一遍 {1, 1, 2} 凑 2 的过程，直到你真正理解为什么是 i > start！加油！