0090. Subsets II ================ 题目信息 -------- :题号: 0090. 子集 II :难度: Medium :主题: 数组、回溯、排序、重复值去重 :原题: `LeetCode 0090 `_ :重点: 从按位置枚举后去重,推导到排序后只跳过同层重复选择 题目重述 -------- 给定一个可能包含重复元素的整数数组 ``nums``,返回它的所有不同子集。 每个输入位置在一个子集中最多使用一次。两个子集只要包含的元素及其重复次数相同,就视为同一个子集, 不能重复返回。答案需要包含空集,子集和答案的排列顺序均不限。 约束为 ``1 <= nums.length <= 10``,``-10 <= nums[i] <= 10``。 自建示例 -------- .. code-block:: text 输入:nums = [1,1,2,2] 输出: [[],[1],[1,1],[2],[2,2],[1,2],[1,1,2],[1,2,2],[1,1,2,2]] 值 1 和 2 都可以分别选择 0、1、2 个,因此共有 ``3 * 3 = 9`` 个不同子集。 .. code-block:: text 输入:nums = [4,4,4] 输出:[[],[4],[4,4],[4,4,4]] 三个位置不同,但数值相同;只需区分选择了几个 4。 .. code-block:: text 输入:nums = [2,5] 输出:[[],[2],[5],[2,5]] 输入没有重复值时,本题退化为普通子集枚举。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: std::vector> bitmaskAndSet(std::vector nums) { std::sort(nums.begin(), nums.end()); std::set> unique; int total = 1 << static_cast(nums.size()); for (int mask = 0; mask < total; ++mask) { std::vector subset; for (int index = 0; index < static_cast(nums.size()); ++index) { if (mask & (1 << index)) { subset.push_back(nums[index]); } } unique.insert(std::move(subset)); } return {unique.begin(), unique.end()}; } void backtrack(const std::vector& nums, int start, std::vector& path, std::vector>& result) { result.push_back(path); for (int index = start; index < static_cast(nums.size()); ++index) { if (index > start && nums[index] == nums[index - 1]) { continue; } path.push_back(nums[index]); backtrack(nums, index + 1, path, result); path.pop_back(); } } std::vector> sortedBacktracking(std::vector nums) { std::sort(nums.begin(), nums.end()); std::vector> result; std::vector path; backtrack(nums, 0, path, result); return result; } std::vector> iterativeExpansion(std::vector nums) { std::sort(nums.begin(), nums.end()); std::vector> result{{}}; int previousSize = 0; for (int index = 0; index < static_cast(nums.size()); ++index) { int oldSize = static_cast(result.size()); int begin = 0; if (index > 0 && nums[index] == nums[index - 1]) { begin = previousSize; } for (int subsetIndex = begin; subsetIndex < oldSize; ++subsetIndex) { std::vector next = result[subsetIndex]; next.push_back(nums[index]); result.push_back(std::move(next)); } previousSize = oldSize; } return result; } public: std::vector> subsetsWithDup(std::vector& nums) { return sortedBacktracking(nums); } }; 题解 ---- 按位置枚举 ~~~~~~~~~~ 忽略重复值时,每个输入位置都有“选择”和“不选择”两种决定,可以用 ``n`` 位掩码枚举全部 ``2^n`` 个位置子集。 重复元素使不同位置选择映射到同一个数值子集。例如在 ``[1,2_a,2_b]`` 中,只选择 ``2_a`` 和 只选择 ``2_b`` 都得到 ``[2]``。朴素方法可以先排序每个子集,再放入集合去重,但它仍生成了所有重复候选, 并承担集合比较和存储成本。 排序后的等价分支 ~~~~~~~~~~~~~~~~ 排序让相同值连续出现。回溯状态 ``backtrack(start)`` 表示:路径已经确定,接下来可以从 ``nums[start:]`` 中选择新的元素。 在同一递归层中,若两个相邻候选值相同,以它们作为“本层首次选择”会产生完全相同的后续数值子集。 因此只保留这一层的第一个等值候选: .. code-block:: cpp if (index > start && nums[index] == nums[index - 1]) { continue; } 条件必须同时检查 ``index > start``。``start`` 是本层第一个候选位置,只有 ``index`` 已越过它时, 前一个相同值才属于同层已经处理过的兄弟分支。 深层重复选择 ~~~~~~~~~~~~ 同层去重不会禁止一个子集包含多个相同值。以 ``[2,2]`` 为例: .. list-table:: :header-rows: 1 * - 状态 - 处理 * - 根层选择第一个 2 - 路径变为 ``[2]``,递归起点移到第二个 2 * - 下一层选择第二个 2 - 此时 ``index == start``,允许形成 ``[2,2]`` * - 根层直接遇到第二个 2 - 此时 ``index > start`` 且与前一项相同,跳过重复兄弟分支 被删除的是“用另一个相同位置建立同样的首次选择分支”,不是后续合法副本。 递归节点即答案 ~~~~~~~~~~~~~~ 子集没有固定长度,每条当前路径本身都是一个合法答案。进入递归节点时先复制 ``path``,于是根节点自然提交空集, 随后每次加入一个元素都会产生一个更长子集。 路径使用严格递增的下标,因此每个输入位置最多使用一次。选择后递归、返回后弹出,保证兄弟分支共享同一个 ``path`` 容器而不互相污染。 迭代扩展 ~~~~~~~~ 普通子集的迭代构造是:处理新元素时,把它追加到当前所有子集的副本后面,答案数量翻倍。 遇到重复值时,不能再次扩展全部旧子集。设处理前一个相同值之前答案长度为 ``previousSize``,处理完前一个值后 新产生的子集范围为 ``[previousSize, oldSize)``。当前重复值只追加到这一段新子集: .. code-block:: text 第一个 2:扩展此前所有子集 第二个 2:只扩展“刚由第一个 2 产生”的子集 这样分别得到选择一个、两个、三个同值副本的层次,不会再次生成“只选择一个 2”的重复结果。 完整性与唯一性 ~~~~~~~~~~~~~~ 任意不同子集都可按非递减顺序表示,并唯一确定每个不同值选取多少个副本。排序回溯允许在更深层连续选择该值, 因此能生成所需副本数;同一层只保留一个等值首次分支,因此不会出现第二条生成同一多重集的路径。 复杂度 ~~~~~~ 位掩码方法先生成 ``2^n`` 个位置子集,并用集合去重,时间和空间都包含额外的集合维护成本。 排序回溯需要 ``O(n log n)`` 预处理。设所有不同答案包含的元素总数为 ``P``,生成并复制答案需要 ``Theta(P)`` 时间;最坏所有元素互异时 ``P = Theta(n * 2^n)``。递归路径和调用栈为 ``O(n)``, 不计返回结果。迭代方法具有相同的输出量级,并直接使用结果数组扩展。