你好，同学。作为你的教练，今天我们来剖析组合搜索中一个非常经典的进阶模型——组合总和 (Combination Sum)。

这道题（对应力扣 LCR 081 / 39 题）在 NOI 竞赛中属于“完全背包搜索版”，是理解搜索树分叉逻辑和无限状态转移的基础。

一、 题目描述 (NOI 风格)

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

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

注意：

1. $A$ 中的数字可以无限制重复被选取。
2. 只要两个组合中元素的出现频率不同，则视为不同的组合。
3. 如果两个组合仅是内部顺序不同，则视为同一个组合。
4. 你可以按任意顺序输出这些组合。

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

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

【样例输入】

4 7
2 3 6 7

【样例输出】

2 2 3
7

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 30$，$1 \le A[i] \le 200$，$1 \le T \le 500$。 序列 $A$ 中的元素互不相同。

二、 预备知识点

1. 深度优先搜索 (DFS) 与回溯：这是解决所有“所有方案”类问题的通用框架。
2. 完全性搜索逻辑：理解在搜索树中，如何通过不移动指针来实现“无限次选取”。
3. 可行性剪枝 (Pruning)：在搜索过程中提前判断当前路径是否已失效。
4. 排序优化：为了提高剪枝效率，通常需要对原始序列进行排序。

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

现在，请拿起笔，我们在草稿纸上画出决策逻辑。

1. 状态转移图 (State Space Tree)

假设 $A = \{2, 3\}$，目标和 $T = 5$。

• 第 1 层：选 2。
• 第 2 层（关键点）：因为可以无限选，你依然有两个分支——选 2 或选 3。
  • 分支 A（继续选 2）：当前和为 4，继续往下。
  • 分支 B（尝试选 3）：当前和为 5，达成目标！记录方案 $\{2, 3\}$。
• 第 3 层（接分支 A）：
  • 若选 2：和为 6，超过 5。剪枝！回溯。

2. 如何避免重复组合？

如果我们在选了 3 之后又回头去选 2，就会产生 $\{3, 2\}$，这与 $\{2, 3\}$ 重复。 技巧：在搜索时，规定一个“非降序”规则。即每次搜索只能从当前索引或更大的索引开始选取，绝对不往回看。

四、 复杂度分析思考

• 时间复杂度分析：
  • 理论上这是一个指数级的过程。状态数的上限取决于目标值 $T$ 与数组中最小元素 $min(A)$ 的比值。
  • 虽然解的个数可能非常多，但在 $T=500$ 且元素 $\ge 1$ 的限制下，大部分分支会因为和超过 $T$ 而迅速被剪枝。
• 空间复杂度分析：
  • 递归深度最深为 $T/min(A)$ 层。
  • NOI 考场建议：不要存储所有结果再输出，如果内存限制紧，可以“搜到一个打印一个”。

五、 算法流程图 (C++14 风格伪代码)

我们使用基于索引和剩余总和的回溯法。请注意 Mermaid 节点中已回避特殊符号。

graph TD
    Start(开始) --> SortAction(对序列 A 执行从小到大排序)
    SortAction --> Init(初始化路径数组 path)
    Init --> CallDFS(调用 DFS 函数 remain 等于 T 且 start 等于 0)

    subgraph DFS_Function [递归搜索函数]
    Check{remain 等于 0 ?}
    Check -- 是 --> Save(记录当前 path 序列并返回)
    Check -- 否 --> LoopInit(循环 i 从 start 到 n 减 1)
    
    LoopInit --> Prune{A-i 大于 remain ?}
    Prune -- 是 --> LoopEnd(当前及后续数字均过大 退出循环)
    Prune -- 否 --> Action(将 A-i 存入 path)
    
    Action --> Recur(调用 DFS 函数 remain 减 A-i 且 start 等于 i)
    note("注意: 传入 i 而非 i 加 1 以实现无限选取")
    
    Recur --> Pop(执行回溯 path-pop_back)
    Pop --> NextI(i 增加 1 继续循环)
    NextI --> LoopInit
    end

    LoopEnd --> Return((返回上一层))
    Save --> Return

六、 读题关键词总结 (NOI 避坑指南)

在做搜索题时，如果读到以下词汇，要立刻联想相应的策略：

1. “无重复正整数”：说明输入很简单，不需要预先处理重复元素。
2. “无限制重复选取”：这是最高级别的信号。它意味着在递归调用时，下一层的起始位置 start 应该是当前索引 i，而不是 i + 1。
3. “唯一组合”：意味着你必须控制搜索顺序（如升序搜索），避免出现不同顺序的同一集合。
4. “所有”：暗示这是一个搜索全集的题目，通常不适合用动态规划（因为 DP 只能求数量或极值，很难存所有方案）。

教练寄语： 同学，这道题的精髓在于对“递归分支控制”的理解。如果你把 DFS(remain - A[i], i) 写成了 DFS(remain - A[i], 0)，你会陷入死循环；写成了 DFS(remain - A[i], i + 1)，你就变成了解决 0/1 背包。那一处细小的索引处理，就是算法功底的体现。加油！