你好，同学。作为你的教练，今天我们来攻克组合搜索（Combination Search）中的一个进阶难点——含有重复元素的组合问题。

这道题在 NOI 竞赛中属于“带约束的回溯搜索”，是考察选手对 搜索树剪枝（Pruning） 理解深度的经典题目。

一、 题目描述 (NOI 风格)

题目名称：组合总和 II (Combination Sum II) 时间限制：1.0s 内存限制：256MB

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

注意：

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

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

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

【样例输入】

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 C[i] \le 50$，$1 \le T \le 30$。

二、 预备知识点

1. 回溯算法 (Backtracking)：通过递归枚举所有可能，并在不满足条件时回退。
2. 树层剪枝 (Tree-level Pruning)：在搜索树的同一层过滤掉相同的数值，防止产生重复组合。
3. 排序 (Sorting)：处理重复元素的前置动作，使相同的数字相邻。

三、 启发式思路引导：草稿纸上的推理

请拿出你的草稿纸，我们要解决的核心矛盾是：输入里有重复的 1，但输出里不能有重复的 {1, 7}。

1. 排序的必要性

在草稿纸上写下：10, 1, 2, 7, 6, 1, 5。 排序后变成：1, 1, 2, 5, 6, 7, 10。 思考：为什么要排序？只有排了序，相同的数字才会“排排坐”，我们才能一眼看出当前选的数字是否和刚才选过的一样。

2. “选与不选”的决策树

假设 $T=8$，我们开始填第一个坑：

• 填 1（第一个 1）：剩下的坑用 {1, 2, 5, 6, 7, 10} 去填。
• 填 1（第二个 1）：注意！ 如果此时再填一次 1 开启新分支，它能搜出来的组合，第一个 1 肯定都搜过了。
• 结论：在同一个坑位（同一层递归），如果前一个数字和当前数字相同，当前这个分支就得砍掉。

3. 区分“树层”与“树枝”

• 树枝（纵向）：第一个坑选了 1，第二个坑选剩下的那个 1。允许！（因为每个数字可以用一次，现在有两个 1）。
• 树层（横向）：第一个坑尝试选第一个 1 失败了（或结束后），第一个坑再尝试选第二个 1。禁止！（会造成重复）。

四、 复杂度分析思考过程

• 时间复杂度：

  • 理论上限是 $O(2^n \cdot n)$，因为每个元素都有选或不选两种可能。
  • 但在 NOI 考场上，由于 $T$ 很小（$T=30$）且 $C[i]$ 为正整数，搜索深度受到极大限制。
  • 优化建议：排序后，若当前数字已大于剩余所需总和，直接 break 掉循环，这就是“可行性剪枝”。

• 空间复杂度：

  • $O(n)$，主要是递归调用的系统栈开销以及存储当前路径的数组。

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

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

graph TD
    Start(开始) --> SortAction("对序列 C 从小到大排序")
    SortAction --> Init("初始化 path 数组, 结果集为空")
    Init --> CallDFS("调用 DFS-目标值T-起点0")

    subgraph DFS_Logic ["递归函数 DFS(remain, start)"]
    CheckZero{"remain == 0 ?"}
    CheckZero -- 是 --> Save("记录当前 path 结果并返回")
    CheckZero -- 否 --> LoopInit("循环 i 从 start 到 n-1")
    
    LoopInit --> Prune1{"C(i) > remain ?"}
    Prune1 -- 是 --> Break("剪枝: 后面数字更大, 退出循环")
    
    Prune1 -- 否 --> Prune2{"i > start 且 C(i) == C(i-1) ?"}
    Prune2 -- 是 --> NextI("跳过: continue 进入下一次 i 循环")
    
    Prune2 -- 否 --> Action("将 C(i) 放入 path")
    Action --> Recur("递归 DFS(remain - C(i), i + 1)")
    Recur --> Pop("回溯: path.pop_back")
    Pop --> NextI
    end

    Save --> Return((返回))
    Break --> Return
    NextI --> LoopEnd{循环结束?}
    LoopEnd -- 是 --> Return

六、 读题理解关键词总结

在 NOI 考场上，看到以下关键词要形成条件反射：

1. “可能包含重复数字”：暗示必须先执行 sort。
2. “每个数字只能使用一次”：意味着递归下一层时，start 参数应传入 i + 1（即不能原地踏步）。
3. “不能包含重复的组合”：这是最核心的去重信号，暗示需要使用 if (i > start && C[i] == C[i-1]) 进行树层剪枝。
4. “正整数”且“目标和”：暗示可以利用单调性进行越界剪枝（如果当前数字已经太大，就没必要往后看了）。

教练寄语： 这道题是搜索算法中“去重”逻辑的最高体现。很多选手会混淆 i > 0 和 i > start，记住：i > start 才是精准定位“同一层”的武器。只要你画对了那棵决策树，你就掌握了 NOI 搜索题的半壁江山。加油！