0216. Combination Sum III ======================== 题目信息 -------- :题号: 0216. 组合总和 III :难度: Medium :主题: 回溯、组合枚举、剪枝、状态恢复 :原题: `LeetCode 0216 `_ :重点: 递增组合、恰好 K 个、剩余和、可达范围剪枝 题目重述 -------- 从数字 ``1`` 到 ``9`` 中恰好选择 ``k`` 个不同数字,使它们的总和等于 ``n``,返回所有满足条件的组合。 同一组数字的不同排列只算一组;结果中的数字按递增顺序排列,每个数字最多使用一次。``k`` 在 ``[1,9]``, ``n`` 在 ``[1,60]``,返回顺序不限。 自建示例 -------- ``k=3,n=9`` 的结果为 ``[[1,2,6],[1,3,5],[2,3,4]]``。``[2,1,6]`` 和 ``[1,2,6]`` 使用同一组数字,不能重复返回。 ``k=2,n=17`` 只有 ``[8,9]``;``k=3,n=7`` 只有 ``[1,2,4]``;``k=3,n=5`` 返回空数组, 因为三个不同正整数的最小和 ``1+2+3=6`` 已经超过目标。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: static int smallestSum(int start, int count) { int sum = 0; for (int value = start; value < start + count; ++value) sum += value; return sum; } static int largestSum(int count) { int sum = 0; for (int value = 9; value > 9 - count; --value) sum += value; return sum; } static void dfsWithoutBounds(int next, int slots, int remaining, std::vector& path, std::vector>& answer) { if (slots == 0) { if (remaining == 0) answer.push_back(path); return; } for (int value = next; value <= 9; ++value) { path.push_back(value); dfsWithoutBounds(value + 1, slots - 1, remaining - value, path, answer); path.pop_back(); } } static void dfsPruned(int next, int slots, int remaining, std::vector& path, std::vector>& answer) { if (slots == 0) { if (remaining == 0) answer.push_back(path); return; } if (remaining < 0 || 9 - next + 1 < slots) return; if (remaining < smallestSum(next, slots) || remaining > largestSum(slots)) { return; } for (int value = next; value <= 9; ++value) { if (value > remaining) break; path.push_back(value); dfsPruned(value + 1, slots - 1, remaining - value, path, answer); path.pop_back(); } } public: std::vector> combinationSum3(int k, int n) { std::vector> answer; std::vector path; dfsPruned(1, k, n, path, answer); return answer; } }; 题解 ---- 从子集和排列中删除重复 ~~~~~~~~~~~~~~~~~~~~~~~~ 把 1 到 9 的每个数字标记为选或不选,可以枚举 ``2^9`` 个子集,再检查选中数量和总和;它不会漏解,却没有利用“组合不计顺序”。 若每层从所有数字任意挑选,还会为同一组数字生成 ``k!`` 种排列,再依靠排序或集合去重。 回溯按递增顺序选择候选。状态中的 ``next`` 表示下一层只能从哪个数字开始,选择 ``value`` 后递归到 ``value+1``; 这样路径天然严格递增,同一组数字只有一条生成路径,``next`` 同时替代了 ``used`` 数组和结果去重集合。 状态定义与剪枝 ~~~~~~~~~~~~~~ ``dfs(next, slots, remaining)`` 表示当前 ``path`` 已经是合法递增前缀,还需要从 ``[next,9]`` 选择 ``slots`` 个数字, 使它们的和为 ``remaining``。进入函数时保持: * ``path.size() == k - slots``,路径严格递增且没有重复; * ``path`` 的和为 ``n - remaining``; * 小于 ``next`` 的数字已经决定,不会在后续重新出现。 如果可用数字不足 ``slots`` 个,分支不可能完成;若 ``slots==0``,只有 ``remaining==0`` 才能收集路径。 进一步从 ``next`` 取最小的 ``slots`` 个数得到未来最小和,从 9 向下取最大的 ``slots`` 个数得到未来最大和; 若 ``remaining`` 不在这个闭区间内,整棵后续搜索树都可以删除。循环中当 ``value > remaining`` 时也可停止, 因为后续候选更大且所有数字为正。 上界从 9 开始计算可能比“从 ``next`` 开始还能拿到的最大和”宽松,但它始终是安全上界:可用数字越少只会让真实最大和更小, 不会把可行分支误判为不可行。候选域固定为 1 到 9,这个常数级计算换来的是在递归入口一次性判断整棵子树。 递增回溯如何覆盖且只覆盖组合 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 在任意状态,目标组合的下一位一定是 ``[next,9]`` 中的某个数字。循环逐一尝试候选,递归负责更大的后缀, 所以任何递增组合都会沿其唯一的数字顺序被走到。反过来,递归参数改为 ``value+1``,使后续数字严格更大, 因此生成的每条路径都合法且不会把同一组数字换顺序再次生成。 以 ``k=3,n=9`` 为例,选择 1 后下一层从 2 开始,可以生成 ``[1,2,6]`` 和 ``[1,3,5]``;回溯弹出 1 后选择 2, 下一层从 3 开始生成 ``[2,3,4]``,不会重复生成以 1 开头的组合。 上下界剪枝删除了哪部分搜索 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 不做剪枝时,``dfsWithoutBounds`` 会继续走完所有递增的 ``k`` 元子集,即使剩余和已经不可能变成 0。 例如进入 ``dfs(1,3,5)`` 时,未来最小和为 6,所有分支都只会更大,整个调用可以立即返回;若还需 3 个数字但最大可取和 ``9+8+7=24`` 仍小于剩余目标,也同样不必展开。 这些上下界只使用候选集合的单调事实,不依赖某个具体解。它们删除的是整棵不可能子树,而不是在叶节点逐条确认失败, 所以不会跳过合法组合。 状态走读 ~~~~~~~~ 对 ``k=3,n=9``,成功分支和剪枝分支如下: .. list-table:: :header-rows: 1 * - 调用状态 - 选择或判断 - 下一状态 * - ``dfsPruned(1,3,9)`` - 选 1 - ``dfsPruned(2,2,8)``,路径 ``[1]`` * - ``dfsPruned(2,2,8)`` - 选 2 - ``dfsPruned(3,1,6)``,路径 ``[1,2]`` * - ``dfsPruned(3,1,6)`` - 选 6 - ``dfsPruned(7,0,0)``,收集 ``[1,2,6]`` * - 回溯到 ``dfsPruned(2,2,8)`` - 选 3 - 后续剩余 5,继续得到 ``[1,3,5]`` * - ``dfsPruned(1,3,5)`` - 最小未来和 6 大于 5 - 立即返回,不展开子树 ``path.pop_back()`` 必须紧跟递归返回:它撤销当前分支的最后一个选择,使兄弟分支重新看到相同的父状态。 答案保存的是路径副本,之后的回溯不会改变已经收集的组合。 代码演进 ~~~~~~~~ ``dfsWithoutBounds`` 先展示只靠递增约束的完整组合枚举;它删除了排列重复,但仍会访问大量和不可能的状态。 ``dfsPruned`` 增加可用数量、剩余和上下界以及 ``value > remaining`` 的剪枝,主入口选择它以压缩实际搜索。 ``smallestSum`` 和 ``largestSum`` 不改变路径,只负责在进入下一层前证明“剩余槽位是否仍有可能补出目标”。 复杂度与边界 ~~~~~~~~~~~~ 固定候选集只有 9 个数,未剪枝的状态上界为 ``O(2^9)``;每个状态的上下界计算最多循环 9 次,视为常数。递归深度和路径空间为 ``O(k)``, 返回结果空间另计。``k=9``、目标小于最小和或大于最大和、``slots==0`` 等边界都由同一状态转移处理。