## 题目地址

https://leetcode.com/problems/subsets-ii/

## 题目描述

Given a collection of integers that might contain duplicates, nums, 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],
[]
]
``````

## 思路

``````class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &S) {
if (S.empty()) return {};
vector<vector<int>> res(1);
sort(S.begin(), S.end());
int size = 1, last = S[0];
for (int i = 0; i < S.size(); ++i) {
if (last != S[i]) {
last = S[i];
size = res.size();
}
int newSize = res.size();
for (int j = newSize - size; j < newSize; ++j) {
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};
``````

[]
[1]
[2]
[1 2]
[2 2]
[1 2 2]

``````                        []
/          \
/            \
/              \
[1]                []
/       \           /    \
/         \         /      \
[1 2]       [1]       [2]     []
/     \     /   \     /   \    / \
[1 2 2] [1 2]  X   [1]  [2 2] [2] X  []
``````

``````class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &S) {
if (S.empty()) return {};
vector<vector<int>> res;
vector<int> out;
sort(S.begin(), S.end());
getSubsets(S, 0, out, res);
return res;
}
void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int>> &res) {
res.push_back(out);
for (int i = pos; i < S.size(); ++i) {
out.push_back(S[i]);
getSubsets(S, i + 1, out, res);
out.pop_back();
while (i + 1 < S.size() && S[i] == S[i + 1]) ++i;
}
}
};
``````

[]
[1]
[1 2]
[1 2 2]
[2]
[2 2]

## 关键点解析

• 回溯法
• backtrack 解题公式

## 代码

• 语言支持：JS，C++，Python3

JavaScript Code：

``````

/*
* @lc app=leetcode id=90 lang=javascript
*
* [90] Subsets II
*
* https://leetcode.com/problems/subsets-ii/description/
*
* algorithms
* Medium (41.53%)
* Total Accepted:    197.1K
* Total Submissions: 469.1K
* Testcase Example:  '[1,2,2]'
*
* Given a collection of integers that might contain duplicates, nums, 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],
* ⁠ []
* ]
*
*
*/
function backtrack(list, tempList, nums, start) {
list.push([...tempList]);
for(let i = start; i < nums.length; i++) {
// 和78.subsets的区别在于这道题nums可以有重复
// 因此需要过滤这种情况
if (i > start && nums[i] === nums[i - 1]) continue;
tempList.push(nums[i]);
backtrack(list, tempList, nums, i + 1)
tempList.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
const list = [];
backtrack(list, [], nums.sort((a, b) => a - b), 0, [])
return list;
};
``````

C++ Code：

``````class Solution {
private:
void subsetsWithDup(vector<int>& nums, size_t start, vector<int>& tmp, vector<vector<int>>& res) {
res.push_back(tmp);
for (auto i = start; i < nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue;
tmp.push_back(nums[i]);
subsetsWithDup(nums, i + 1, tmp, res);
tmp.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
auto tmp = vector<int>();
auto res = vector<vector<int>>();
sort(nums.begin(), nums.end());
subsetsWithDup(nums, 0, tmp, res);
return res;
}
};
``````

Python Code:

``````class Solution:
def subsetsWithDup(self, nums: List[int], sorted: bool=False) -> List[List[int]]:
"""回溯法，通过排序参数避免重复排序"""
if not nums:
return [[]]
elif len(nums) == 1:
return [[], nums]
else:
# 先排序，以便去重
# 注意，这道题排序花的时间比较多
# 因此，增加一个参数，使后续过程不用重复排序，可以大幅提高时间效率
if not sorted:
nums.sort()
# 回溯法
pre_lists = self.subsetsWithDup(nums[:-1], sorted=True)
all_lists = [i+[nums[-1]] for i in pre_lists] + pre_lists
# 去重
result = []
for i in all_lists:
if i not in result:
result.append(i)
return result
``````

评论
0 评论