0040. Combination Sum II ======================== 题目信息 -------- :题号: 0040. 组合总和 II :难度: Medium :主题: 数组、回溯、排序、同层去重 :原题: `LeetCode 0040 `_ :重点: 从枚举下标子集后去重,推导到排序后跳过同层等值分支,并保证每个位置最多使用一次 题目重述 -------- 给定正整数数组 ``candidates`` 和正整数 ``target``,找出所有元素之和恰好等于 ``target`` 的不同组合。 数组中可以出现相同数值,但每个数组位置在一个组合中最多使用一次。组合只按数值及其出现次数区分,内部顺序不同 不算新组合,因此相同数值组合只能返回一次。答案顺序不限。 ``candidates`` 的长度位于 ``[1, 100]``,每个元素位于 ``[1, 50]``,``target`` 位于 ``[1, 30]``。 自建示例 -------- * ``candidates = [1, 1, 1, 2]``、``target = 3``,返回 ``[[1, 1, 1], [1, 2]]``;三个 ``1`` 来自 三个不同位置,因此可以同时使用; * ``candidates = [2, 5, 2, 1, 2]``、``target = 5``,返回 ``[[1, 2, 2], [5]]``;三个位置上的 ``2`` 不应制造多份 ``[1, 2, 2]``; * ``candidates = [3, 4, 7]``、``target = 2``,返回 ``[]``;排序后首个候选已经超过剩余目标; * ``candidates = [1, 2, 3]``、``target = 3``,返回 ``[[1, 2], [3]]``;同一位置不能在组合中重复使用。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include class Solution { private: void subsetDfs( const std::vector& candidates, int index, int remaining, std::vector& path, std::set>& unique ) { if (remaining == 0) { std::vector canonical = path; std::sort(canonical.begin(), canonical.end()); unique.insert(canonical); return; } if (index == static_cast(candidates.size()) || remaining < 0) { return; } subsetDfs(candidates, index + 1, remaining, path, unique); path.push_back(candidates[index]); subsetDfs( candidates, index + 1, remaining - candidates[index], path, unique ); path.pop_back(); } std::vector> enumerateSubsetsThenDeduplicate( const std::vector& candidates, int target ) { std::set> unique; std::vector path; subsetDfs(candidates, 0, target, path, unique); return {unique.begin(), unique.end()}; } std::vector> buildFrequencyGroups( std::vector candidates ) { std::sort(candidates.begin(), candidates.end()); std::vector> groups; for (int value : candidates) { if (groups.empty() || groups.back().first != value) { groups.push_back({value, 1}); } else { ++groups.back().second; } } return groups; } void frequencyDfs( const std::vector>& groups, int group, int remaining, std::vector& path, std::vector>& result ) { if (remaining == 0) { result.push_back(path); return; } if (group == static_cast(groups.size())) { return; } const auto [value, frequency] = groups[group]; const int maximum = std::min(frequency, remaining / value); for (int used = 0; used <= maximum; ++used) { for (int count = 0; count < used; ++count) { path.push_back(value); } frequencyDfs( groups, group + 1, remaining - used * value, path, result ); for (int count = 0; count < used; ++count) { path.pop_back(); } } } std::vector> searchByFrequencyGroups( std::vector candidates, int target ) { const auto groups = buildFrequencyGroups(std::move(candidates)); std::vector> result; std::vector path; frequencyDfs(groups, 0, target, path, result); return result; } void sameLevelDfs( const std::vector& candidates, 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(candidates.size()); ++index) { if (index > start && candidates[index] == candidates[index - 1]) { continue; } const int value = candidates[index]; if (value > remaining) { break; } path.push_back(value); sameLevelDfs(candidates, index + 1, remaining - value, path, result); path.pop_back(); } } std::vector> sortedSameLevelDeduplication( std::vector candidates, int target ) { std::sort(candidates.begin(), candidates.end()); std::vector> result; std::vector path; sameLevelDfs(candidates, 0, target, path, result); return result; } public: std::vector> combinationSum2( std::vector& candidates, int target ) { return sortedSameLevelDeduplication(candidates, target); } }; 题解 ---- 下标子集基线 ~~~~~~~~~~~~ 每个数组位置只有选与不选两种决定。``subsetDfs`` 处理完下标 ``index`` 后递归到 ``index + 1``,因此任何路径都 不会重复使用同一位置;所有下标子集都会被枚举,所以不会遗漏合法组合。 下标不同却可能表示相同的数值组合。若输入含 ``1a``、``1b`` 和 ``2``,选择 ``{1a, 2}`` 与 ``{1b, 2}`` 是两个下标子集,却都对应 ``[1, 2]``。基线方法只能在命中目标后排序路径,再交给集合删除重复结果。 事后去重保证答案正确,却没有减少搜索:等价下标分支仍被完整展开。优化目标是让相同数值组合只进入搜索树一次。 频次分组模型 ~~~~~~~~~~~~ 排序后可以把相同值压缩为 ``(value, frequency)``。例如 ``[1, 1, 1, 2]`` 变为: .. code-block:: text (1, 3), (2, 1) 处理一组数值时,只需决定使用 ``0..frequency`` 次,并受 ``remaining / value`` 限制。每个组合对应唯一的次数向量, 例如 ``[1, 1, 1]`` 对应 ``(3, 0)``,``[1, 2]`` 对应 ``(1, 1)``,重复下标身份因此消失。 ``searchByFrequencyGroups`` 从状态模型中解决了去重,但每次枚举使用次数都要批量追加和撤销元素。还可以保留下标回溯 模板,只在等价分支出现时直接跳过。 排序后的搜索空间 ~~~~~~~~~~~~~~~~ 主方法先排序数组,再让 ``start`` 表示本层允许选择的最小下标。路径中的下标严格递增,因此路径数值也保持非递减, 同一个组合不会再因元素顺序不同而出现多次。 选择 ``candidates[index]`` 后递归到 ``index + 1``,表示当前位置已经消耗。后面即使还有相同数值,也属于不同位置, 可以在更深层继续选择。这正是本题与可无限复用候选的 0039 的核心差异。 同层等值分支 ~~~~~~~~~~~~ 固定相同的 ``path``、``start`` 和 ``remaining`` 时,若本层先选择两个相邻等值位置中的前一个或后一个,形成的数值 前缀完全相同。后一个位置可使用的后缀还更短,不可能产生前一个分支无法产生的新数值组合,因此跳过: .. code-block:: cpp if (index > start && candidates[index] == candidates[index - 1]) { continue; } ``index > start`` 把去重限制在同一递归层。进入下一层后,后一个等值位置可能是该层第一个候选,必须允许选择,否则 会错误删除 ``[1, 1]``、``[1, 1, 1]`` 等合法组合。 以 ``[1a, 1b, 1c, 2]``、目标 ``3`` 为例:根层只从 ``1a`` 开始等值分支;第二层仍可选 ``1b``,第三层仍可 选 ``1c``,得到 ``[1, 1, 1]``;第二层也可跳到 ``2``,得到 ``[1, 2]``。 任意合法组合按非递减顺序表示后,都可以依次选择每层最早可用的对应下标,因此不会遗漏。若两条路径生成相同组合, 它们第一次选择不同下标时必然处于同层且数值相同,较后的分支会被上述条件跳过,因此组合也不会重复。 剩余目标剪枝 ~~~~~~~~~~~~ 所有候选均为正数。排序后若当前 ``value > remaining``,后续值只会更大,本层不可能再命中目标,可以直接 ``break``。选择一个候选后,``remaining`` 严格减小;当它变为零时,当前路径恰好构成答案。 每轮递归开始时保持三个状态:路径使用的下标严格递增,路径数值非递减,``remaining`` 等于目标减去路径和。 同层去重只删除等价首选,``index + 1`` 保证位置不复用,正数剪枝只排除必然超出剩余目标的后缀。 状态演化 ~~~~~~~~ 对排序后的 ``[1, 2, 2, 2, 5]``、目标 ``5``: .. list-table:: :header-rows: 1 * - 路径 - ``start`` - 本层动作 - 结果 * - ``[]`` - 0 - 选择 ``1`` - 剩余 ``4`` * - ``[1]`` - 1 - 选择第一个 ``2`` - 剩余 ``2`` * - ``[1, 2]`` - 2 - 选择下一个 ``2`` - 得到 ``[1, 2, 2]`` * - ``[1]`` - 1 - 跳过本层其余等值 ``2`` - 不生成重复组合 * - ``[]`` - 0 - 选择 ``5`` - 得到 ``[5]`` 代码演进 ~~~~~~~~ ``enumerateSubsetsThenDeduplicate`` 严格执行每个位置只使用一次,但先搜索全部等价分支,再用集合去重。 ``searchByFrequencyGroups`` 把相同值压缩为使用次数,从状态定义中删除重复下标身份。 ``sortedSameLevelDeduplication`` 保留下标回溯结构,通过排序、同层跳过和 ``index + 1`` 同时实现结果去重与位置单次 使用,并利用正数有序性提前结束无效后缀。公开入口采用该方法。 复杂度分析 ~~~~~~~~~~ 设输入长度为 ``n``。排序需要 ``O(n log n)``。下标子集方法最多访问 ``2^n`` 个选择状态,规范化答案还需要路径 排序与集合插入。 频次分组若各数值出现次数为 ``f_1, f_2, ...``,忽略和值剪枝时最多枚举 ``(f_1 + 1)(f_2 + 1)...`` 个次数状态。主方法的搜索树最坏仍可达到 ``O(2^n)``,但同层去重与正数剪枝会删除 大量状态。除输出外,递归栈与路径最多保存 ``n`` 个元素,额外空间为 ``O(n)``。