class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
}
};
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10相似题目
原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-24 10:54:31
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
def back_tracking(temp, start):
res.append(temp[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
temp.append(nums[i])
back_tracking(temp, i+1)
temp.pop()
back_tracking([], 0)
return res
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2022-11-24 10:53:46
// 递归法
func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
t := []int{}
var dfs func(bool, int)
dfs = func(choosePre bool, cur int) {
if cur == len(nums) {
ans = append(ans, append([]int(nil), t...))
return
}
dfs(false, cur+1)
if !choosePre && cur > 0 && nums[cur-1] == nums[cur] {
return
}
t = append(t, nums[cur])
dfs(true, cur+1)
t = t[:len(t)-1]
}
dfs(false, 0)
return
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2022-11-24 10:53:21
func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
outer:
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
for i, v := range nums {
if mask>>i&1 > 0 {
if i > 0 && mask>>(i-1)&1 == 0 && v == nums[i-1] {
continue outer
}
t = append(t, v)
}
}
ans = append(ans, append([]int(nil), t...))
}
return
}