0077. Combinations ================== 题目信息 -------- :题号: 0077. 组合 :难度: Medium :主题: 回溯、组合、容量剪枝 :原题: `LeetCode 0077 `_ :重点: 从枚举全部子集,推导到递增路径回溯,再利用剩余容量收紧候选上界 题目重述 -------- 给定两个整数 ``n`` 和 ``k``,从集合 ``{1, 2, ..., n}`` 中选出恰好 ``k`` 个不同整数, 返回所有可能的组合。 组合只关心选中了哪些整数,不关心排列顺序。例如 ``[1, 3]`` 与 ``[3, 1]`` 表示同一个组合, 只能返回一次。答案中的组合顺序不限,每个组合内部的元素顺序也不限。 约束为 ``1 <= n <= 20``、``1 <= k <= n``。 自建示例 -------- .. code-block:: text 输入:n = 4, k = 3 输出:[[1,2,3],[1,2,4],[1,3,4],[2,3,4]] 四个整数中任取三个,共有 ``C(4,3)=4`` 个组合。 .. code-block:: text 输入:n = 3, k = 1 输出:[[1],[2],[3]] 每个单独的整数都构成一个合法组合。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: int countBits(int mask) { int count = 0; while (mask != 0) { mask &= mask - 1; ++count; } return count; } std::vector> maskEnumeration(int n, int k) { std::vector> result; const int limit = 1 << n; for (int mask = 0; mask < limit; ++mask) { if (countBits(mask) != k) { continue; } std::vector combination; for (int bit = 0; bit < n; ++bit) { if ((mask & (1 << bit)) != 0) { combination.push_back(bit + 1); } } result.push_back(combination); } return result; } void plainDfs(int start, int n, int k, std::vector& path, std::vector>& result) { if (static_cast(path.size()) == k) { result.push_back(path); return; } for (int value = start; value <= n; ++value) { path.push_back(value); plainDfs(value + 1, n, k, path, result); path.pop_back(); } } void prunedDfs(int start, int n, int k, std::vector& path, std::vector>& result) { if (static_cast(path.size()) == k) { result.push_back(path); return; } const int needed = k - static_cast(path.size()); const int lastStart = n - needed + 1; for (int value = start; value <= lastStart; ++value) { path.push_back(value); prunedDfs(value + 1, n, k, path, result); path.pop_back(); } } public: std::vector> combine(int n, int k) { std::vector> result; std::vector path; path.reserve(k); prunedDfs(1, n, k, path, result); return result; } }; 题解 ---- 全部子集枚举 ~~~~~~~~~~~~ ``1..n`` 的每个子集都可由一个 ``n`` 位掩码表示:第 ``bit`` 位为 1,表示选择 ``bit+1``。 枚举 ``0`` 到 ``2^n-1``,再保留恰好含 ``k`` 个置位的掩码,可以直接得到全部组合。 这种方法先访问所有 ``2^n`` 个子集,其中大量子集的大小并非 ``k``。它说明问题可以归结为选择集合, 但没有利用“只需要长度为 ``k`` 的结果”这一条件。 递增路径 ~~~~~~~~ 回溯路径保存当前已经选择的整数。参数 ``start`` 表示下一层只能从 ``start`` 及其右侧继续选择。 选择 ``value`` 后,递归入口变为 ``value+1``,所以路径始终严格递增。 严格递增同时解决两个问题: * 同一个整数不会被再次选择; * 同一个集合只会生成唯一的递增排列。 例如组合 ``{1,3,5}`` 只会沿 ``1 -> 3 -> 5`` 到达,不会生成 ``3 -> 1 -> 5`` 等排列。 选择与恢复 ~~~~~~~~~~ 每次循环执行三个步骤:把候选加入 ``path``,递归枚举包含该候选的全部后续组合,随后弹出该候选。 弹出后,路径恢复到进入本轮循环前的状态,下一候选可以复用同一个容器。 当路径长度达到 ``k`` 时,当前路径已经是完整组合。此时复制到结果并立即返回,避免继续加入多余元素。 容量剪枝 ~~~~~~~~ 无剪枝回溯仍会进入一些不可能填满 ``k`` 个元素的分支。设当前路径还需要: .. code-block:: text needed = k - path.size() 若本层选择 ``value``,从 ``value`` 到 ``n`` 至少要留下 ``needed`` 个可选整数,因此必须满足: .. code-block:: text n - value + 1 >= needed value <= n - needed + 1 所以循环终点可以从 ``n`` 收紧为 ``lastStart = n-needed+1``。超过该上界的候选即使把右侧元素全部选中, 也无法填满路径。 .. list-table:: :header-rows: 1 * - 当前路径 - 还需数量 - 本层最大候选 * - ``[]``,``n=5,k=3`` - 3 - 3 * - ``[1]`` - 2 - 4 * - ``[1,4]`` - 1 - 5 * - ``[1,4,5]`` - 0 - 提交结果 完整性 ~~~~~~ 任意合法组合都有唯一的递增表示 ``a1 < a2 < ... < ak``。算法从 1 开始,在第 ``i`` 层选择 ``ai``, 随后只搜索更大的整数,因此存在一条递归路径能够依次选中整个组合。 容量剪枝只排除“剩余元素数量不足”的起点。合法组合的每个前缀后都至少保留了完成该组合所需的元素, 所以这条路径不会被剪掉。 唯一性 ~~~~~~ 每条叶子路径都是严格递增序列。一个集合只有一种严格递增排列,因此不同叶子不可能表示同一个组合, 结果中不会出现重复项。 复杂度 ~~~~~~ 位掩码方法枚举 ``2^n`` 个子集,并可能扫描 ``n`` 位,时间 ``O(2^n * n)``。 剪枝回溯输出 ``C(n,k)`` 个组合,每个组合复制 ``k`` 个整数,输出主导时间为 ``O(C(n,k) * k)``。递归路径最多保存 ``k`` 个整数,不计返回结果时额外空间为 ``O(k)``。