labuladong讲解

你好，同学。欢迎来到 NOI 专题进阶课。之前我们处理的都是“每个元素只能用一次”的组合问题。今天我们要挑战一个更灵活的模型——组合总和 (Combination Sum)。

这道题的精髓在于无限制重复选取。在 NOI 竞赛中，这属于“不限次选取的组合搜索”，也是理解“完全背包搜索版”逻辑的重要题目。

一、 题目描述 (NOI 风格)

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

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

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

【输入格式】 输入共两行。 第一行包含两个整数 $n$ 和 $T$。$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 40$，$1 \le T \le 40$。 序列 $A$ 中的元素互不相同。

二、 预备知识点

1. 回溯算法 (Backtracking)：通过递归枚举所有可能。
2. 完全背包搜索模型：理解“同一个元素可以多次进入搜索路径”的逻辑。
3. 排序剪枝 (Pruning)：在搜索前进行排序，若当前和已超标，则后续更大的数无需尝试。
4. 去重技巧：通过维护搜索的“起始索引”来避免产生如 {2, 3, 2} 和 {2, 2, 3} 这样的重复组合。

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

假设候选数是 {2, 3, 6, 7}，目标是 7。

1. 决策树的构建

在草稿纸上画出搜索树，重点在于如何体现“无限次选取”：

• 第 1 层：选 2。
• 第 2 层：由于可以重复选，我们依然可以选 2。
• 第 3 层：依然可以选 2。
• 第 4 层：再选 2，总和为 8，超过 7。回溯！
• 回到第 3 层：不选 2 了，尝试选 3。总和 2+2+3 = 7。记录解！回溯！

2. 如何避免重复？

如果你选了 3 之后再回头选 2，就会出现 {3, 2, 2}。 策略：为了保证组合唯一，我们规定：一旦开始尝试第 $i$ 个数，就绝对不再回头看第 $i-1$ 个数。 但在当前这一步，你仍然可以继续选第 $i$ 个数。

四、 复杂度分析与建议

• 时间复杂度：

  • 理论上这是一个指数级的搜索空间。
  • 但在 NOI 竞赛中，由于 $T$ 只有 40 且最小元素通常 $\ge 1$，搜索树的深度有限。
  • 优化建议：必须排序。排序后，如果在 for 循环中发现 target - A[i] < 0，可以直接 break 掉当前循环，这能砍掉大量的无效分支。

• 空间复杂度：

  • 递归深度最大为 $T$（当序列中有 1 时）。
  • 路径数组占用 $O(T)$。

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

我们使用基于索引的回溯法来实现。注意：Mermaid 语法中括号已通过描述避开。

graph TD
    Start(开始) --> SortAction("对序列 A 进行从小到大排序")
    SortAction --> Init("初始化 path 数组")
    Init --> CallDFS("调用 DFS(当前剩余目标 T, 起始索引 0)")

    subgraph DFS_Process [递归函数 DFS-remain-start]
    CheckBase{remain 等于 0 ?}
    CheckBase -- Yes --> Output("记录并保存当前 path 并返回")
    CheckBase -- No --> LoopInit("循环 i 从 start 到 n-1")
    
    LoopInit --> Prune{A-i 大于 remain ?}
    Prune -- Yes --> LoopEnd("当前数太大, 直接跳出循环(剪枝)")
    Prune -- No --> Action("将 A-i 放入 path")
    
    Action --> Recur("递归 DFS(remain - A-i, i)")
    note("注意: 传入 i 而非 i+1 实现了无限次选取")
    
    Recur --> Pop("回溯: path.pop_back")
    Pop --> NextI("i++ 继续循环")
    NextI --> LoopInit
    end

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

六、 读题关键词总结

在 NOI 竞赛中处理“和为定值”的搜索题，请重点扫描这些关键词：

1. “无限制重复选取” (Unlimited usage)：这是最高级别的信号。它意味着在递归调用时，下一层的起始索引 start 应该是当前索引 i，而不是 i + 1。
2. “唯一组合” (Unique combinations)：这提示你不能走回头路。搜索顺序必须是单向的（例如索引递增）。
3. “无重复元素” (Distinct integers)：这降低了难度，不需要在搜索层内做复杂的 nums[i] == nums[i-1] 的去重判断。
4. “正整数” (Positive integers)：这是剪枝的前提。因为数字是正的，所以“和”只会越来越大，一旦超过目标值就可以立刻停止。

教练寄语： “组合总和”是掌握完全组合搜索的必修课。这道题最核心的一行代码就在递归调用里：到底是 dfs(i) 还是 dfs(i+1)？理解了这个索引的含义，你就理解了搜索状态空间的转移。去草稿纸上模拟一下 {2, 3} 凑 5 的过程吧！加油！