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