0039. Combination Sum ===================== 题目信息 -------- :题号: 0039. 组合总和 :难度: Medium :主题: 数组、回溯、组合搜索、剪枝 :原题: `LeetCode 0039 `_ :重点: 从枚举有序选择序列,推导到只生成非递减组合,并允许同一候选值重复使用 题目重述 -------- 给定一个由互不相同正整数组成的数组 ``candidates`` 和一个正整数 ``target``,找出所有元素之和恰好等于 ``target`` 的不同组合。 每个候选值可以在同一个组合中使用任意多次。组合只由各数值的使用次数决定,内部排列顺序不产生新答案;例如 ``[2, 2, 3]``、``[2, 3, 2]`` 和 ``[3, 2, 2]`` 属于同一个组合。答案顺序不限。 ``candidates`` 的长度位于 ``[1, 30]``,每个候选值位于 ``[2, 40]``,``target`` 位于 ``[1, 40]``。题目保证 不同合法组合的数量少于 150。 自建示例 -------- * ``candidates = [2, 3, 6, 7]``、``target = 7``,返回 ``[[2, 2, 3], [7]]``; * ``candidates = [2, 3, 5]``、``target = 8``,返回 ``[[2, 2, 2, 2], [2, 3, 3], [3, 5]]``; * ``candidates = [3]``、``target = 9``,返回 ``[[3, 3, 3]]``,说明同一候选可以重复使用; * ``candidates = [5, 8, 11]``、``target = 3``,返回 ``[]``,因为所有候选都大于目标; * ``candidates = [4, 6, 9]``、``target = 18``,返回 ``[[4, 4, 4, 6], [6, 6, 6], [9, 9]]``,排列不同不会重复计入。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: void enumerateSequences( const std::vector& values, int remaining, std::vector& path, std::set>& uniqueCombinations ) { if (remaining == 0) { std::vector canonical = path; std::sort(canonical.begin(), canonical.end()); uniqueCombinations.insert(canonical); return; } for (int value : values) { if (value > remaining) { break; } path.push_back(value); enumerateSequences(values, remaining - value, path, uniqueCombinations); path.pop_back(); } } std::vector> enumerateAndDeduplicate( std::vector candidates, int target ) { std::sort(candidates.begin(), candidates.end()); std::set> uniqueCombinations; std::vector path; enumerateSequences(candidates, target, path, uniqueCombinations); return {uniqueCombinations.begin(), uniqueCombinations.end()}; } void enumerateCounts( const std::vector& values, int index, int remaining, std::vector& path, std::vector>& result ) { if (remaining == 0) { result.push_back(path); return; } if (index == static_cast(values.size())) { return; } const int value = values[index]; const int maximumCount = remaining / value; const int originalSize = static_cast(path.size()); for (int count = 0; count <= maximumCount; ++count) { path.resize(originalSize); path.insert(path.end(), count, value); enumerateCounts( values, index + 1, remaining - count * value, path, result ); } path.resize(originalSize); } std::vector> countByCandidate( std::vector candidates, int target ) { std::sort(candidates.begin(), candidates.end()); std::vector> result; std::vector path; enumerateCounts(candidates, 0, target, path, result); return result; } void orderedSearch( const std::vector& values, int start, int remaining, std::vector& path, std::vector>& result ) { if (remaining == 0) { result.push_back(path); return; } for (int index = start; index < static_cast(values.size()); ++index) { const int value = values[index]; if (value > remaining) { break; } path.push_back(value); orderedSearch(values, index, remaining - value, path, result); path.pop_back(); } } std::vector> orderedBacktracking( std::vector candidates, int target ) { std::sort(candidates.begin(), candidates.end()); std::vector> result; std::vector path; orderedSearch(candidates, 0, target, path, result); return result; } public: std::vector> combinationSum( std::vector& candidates, int target ) { return orderedBacktracking(candidates, target); } }; 题解 ---- 直接枚举选择序列 ~~~~~~~~~~~~~~~~ 最直接的搜索把状态写成“还差多少”:初始 ``remaining = target``,每层可以选择任意一个不超过剩余值的候选,随后 递归搜索 ``remaining - value``。所有候选都是正数,所以剩余值严格下降,搜索一定终止;降到零时,当前路径的和 恰好等于目标。 问题在于这棵树生成的是有顺序的选择序列。对 ``candidates = [2, 3]``、``target = 7``,会出现三条成功路径: .. code-block:: text 2 -> 2 -> 3 2 -> 3 -> 2 3 -> 2 -> 2 它们对应同一个组合 ``[2, 2, 3]``。``enumerateAndDeduplicate`` 在叶节点把路径排序,再放入集合,因此结果正确; 大量等价排列已经被完整搜索,最后才被删除,搜索和集合比较都属于重复工作。 按每种候选的使用次数搜索 ~~~~~~~~~~~~~~~~~~~~~~~~ 组合不关心选取顺序,只关心每个候选用了多少次。``countByCandidate`` 因此依次处理候选值,并为当前值枚举使用次数 ``0..remaining / value``,随后进入下一个候选。 一条搜索路径实际上确定了一个次数向量。例如 ``values = [2, 3, 5]``、``target = 8`` 时,组合 ``[2, 3, 3]`` 对应: .. code-block:: text 2 使用 1 次 3 使用 2 次 5 使用 0 次 候选值互不相同,所以一个次数向量只对应一个组合;每个组合也有唯一的次数向量,因此这种方法无需集合去重。它的 不足是每层还要显式枚举“当前候选取零次、一次、两次……”,并反复批量追加与删除相同值。 把次数枚举改写为逐元素选择 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 逐元素回溯可以把“当前候选再多取一次”和“转向后面的候选”统一在一个循环中。先将候选升序排列,并给递归状态增加 ``start``:下一次只能选择下标不小于 ``start`` 的候选。 因此路径中的候选下标永不下降,数值序列也保持非递减。选择 ``values[index]`` 后,递归仍传入 ``index``,因为 同一候选允许继续使用;循环进入下一下标时,搜索自然转向更大的候选。 .. code-block:: text 选择 2 后递归起点仍为 2 的下标:可以继续选 2、3、5 选择 3 后递归起点变为 3 的下标:可以继续选 3、5,不能回到 2 选择 5 后递归起点变为 5 的下标:只能继续选 5 若题目规定每个候选只能使用一次,递归起点才应改为 ``index + 1``;本题传入 ``index`` 是允许重复使用的关键。 非递减路径为何恰好去重 ~~~~~~~~~~~~~~~~~~~~~~ 任意合法组合都能唯一写成非递减序列。假设组合中下标 ``i`` 的候选使用若干次,再使用更大下标的候选; ``orderedSearch`` 可以在 ``i`` 处重复选择任意次,再由循环转到更大下标,所以这条规范序列一定能够生成。 反过来,搜索路径的下标从不下降,同一多重集合的其他排列都不可能出现。候选值本身互不相同,因此也不会有两个 不同下标表示同一个数值。每个组合由唯一一条路径生成,既不遗漏,也不需要结果集合去重。 正数与排序如何产生剪枝 ~~~~~~~~~~~~~~~~~~~~~~ 所有候选都是正数,因此选择一个值后 ``remaining`` 必然减小;若某条路径的剩余值无法再由候选凑出,它最终会因没有 可选值而返回。 排序后,循环遇到 ``value > remaining`` 时,当前值已经无法选择,后面的值只会更大,因此可以直接 ``break``, 一次排除整个后缀。若候选包含零或负数,剩余值未必下降,重复使用还可能形成无限搜索,本题的正数条件是终止与剪枝 成立的基础。 选择、递归与撤销 ~~~~~~~~~~~~~~~~ ``path`` 表示当前递归路径已经选取的组合。进入子树前追加候选,子树返回后删除末尾,使下一个兄弟分支重新从同一父 状态开始。``remaining`` 按值传递,无需手动恢复。 当 ``remaining == 0`` 时,代码复制当前 ``path`` 到结果中。保存的是独立副本,因此后续 ``pop_back`` 不会修改 已经记录的答案。 状态演化 ~~~~~~~~ 对 ``candidates = [2, 3, 5]``、``target = 8``,生成 ``[2, 3, 3]`` 的路径如下: .. list-table:: :header-rows: 1 * - ``path`` - ``start`` 可选值 - ``remaining`` - 动作 * - ``[]`` - ``2, 3, 5`` - 8 - 选择 2 * - ``[2]`` - ``2, 3, 5`` - 6 - 转向 3 * - ``[2, 3]`` - ``3, 5`` - 3 - 再次选择 3 * - ``[2, 3, 3]`` - ``3, 5`` - 0 - 记录答案 在选择 3 后,递归不会再访问 2,因此不会生成 ``[3, 2, 3]`` 或 ``[3, 3, 2]``。 代码演进 ~~~~~~~~ 三种方法依次删除两类重复工作: #. ``enumerateAndDeduplicate`` 搜索全部有序选择序列,再把等价排列规范化并交给集合删除; #. ``countByCandidate`` 直接枚举每个候选的使用次数,从搜索空间中消除排列重复; #. ``orderedBacktracking`` 用非递减路径隐式表达使用次数,一次选择一个元素,并利用排序在候选过大时停止循环。 公开入口采用第三种方法。它最直接对应“选择一个候选、继续使用它或转向更大候选”的搜索过程,路径本身已经是答案的 唯一规范表示。 复杂度分析 ~~~~~~~~~~ 设候选数量为 ``m``,最小候选值为 ``a``,任意路径长度最多为 ``d = target / a``。回溯问题的搜索规模依赖候选值与 目标,最坏情况下呈指数增长,可粗略上界为 ``O(m^d)`` 个搜索节点;排序需要 ``O(m log m)``。 每个合法组合复制到结果时还需要与其长度成正比的时间,因此更准确地说,总时间至少包含全部输出元素的数量。递归栈与 当前路径最多保存 ``d`` 个值,除返回结果外的额外空间为 ``O(d)``。直接序列方法还要保存规范化集合,并搜索大量 排列重复;按次数方法的递归深度为 ``O(m)``,路径长度仍最多为 ``O(d)``。