LeetCode 0090 - Subsets II
# Hints
- DFS
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a collection of integers that might contain duplicates, , return all possible subsets (the power set).
Note:
The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
# 题意
给定一个大小为 的可重复集合,求出其所有不同的子集。
# 题解
本题与 LeetCode 0078 的区别在于集合中可能存在重复元素且在求子集时要求去除相同的子集。可以暴力枚举然后用 set 暴力去重,但是时间空间都会很差。我们可以基于 LeetCode 0078 中的 DFS 解法进行优化。
对于第一种 DFS 实现,我们可以用 map 预处理每个元素在集合中的的出现次数,然后在搜索时枚举每个元素的出现次数即可。
对于第二种 DFS 实现,我们首先在搜索前对集合进行排序,然后在遍历时直接跳过相邻的重复元素,即可在搜索时直接排除相同的子集。
时间复杂度仍为 。
# AC代码
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> & nums) {
// 计数
map<int, int> mp;
for (auto x : nums) {
mp[x] ++;
}
vector<pair<int, int>> cnums;
for (auto p : mp) {
cnums.push_back(p);
}
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, vec, res, cnums);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, vector<int> & vec, vector<vector<int>> & res, const vector<pair<int, int>> & cnums) {
// 递归终止
if (depth == cnums.size()) {
res.push_back(vec);
return;
}
// 递归
int num = cnums[depth].first, cnt = cnums[depth].second;
for (int i = 0; i < cnt; i ++) {
vec.push_back(num);
dfs(depth + 1, vec, res, cnums);
}
for (int i = 0; i < cnt; i ++) {
vec.pop_back();
}
dfs(depth + 1, vec, res, cnums);
}
};
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> & nums) {
// 排序
sort(nums.begin(), nums.end());
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, vec, res, nums);
// 返回
return res;
}
// 深度优先搜索
void dfs(int start, vector<int> & vec, vector<vector<int>> & res, const vector<int> & nums) {
// 更新答案
res.push_back(vec);
// 递归
for (int i = start; i < nums.size(); i ++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
vec.push_back(nums[i]);
dfs(i + 1, vec, res, nums);
vec.pop_back();
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01