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相似题目
原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2025-02-05 09:26:31
impl Solution {
pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort_unstable();
fn dfs(mut i: usize, nums: &[i32], ans: &mut Vec<Vec<i32>>, path: &mut Vec<i32>) {
if i == nums.len() {
ans.push(path.clone());
return;
}
// 选 x
let x = nums[i];
path.push(x);
dfs(i + 1, nums, ans, path);
path.pop(); // 恢复现场
// 不选 x，那么后面所有等于 x 的数都不选
// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i += 1;
while i < nums.len() && nums[i] == x {
i += 1;
}
dfs(i, nums, ans, path);
}
let mut ans = vec![];
let mut path = vec![];
dfs(0, &nums, &mut ans, &mut path);
ans
}
// 枚举选哪个
pub fn subsets_with_dup2(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort_unstable();
fn dfs(i: usize, nums: &[i32], ans: &mut Vec<Vec<i32>>, path: &mut Vec<i32>) {
ans.push(path.clone());
// 在 [i,n-1] 中选一个 nums[j]
// 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for j in i..nums.len() {
// 如果 j>i，说明 nums[j-1] 没有选
// 同方法一，所有等于 nums[j-1] 的数都不选
if j > i && nums[j] == nums[j - 1] {
continue;
}
path.push(nums[j]);
dfs(j + 1, nums, ans, path);
path.pop(); // 恢复现场
}
}
let mut ans = vec![];
let mut path = vec![];
dfs(0, &nums, &mut ans, &mut path);
ans
}
}
javascript 解法, 执行用时: 2 ms, 内存消耗: 53.1 MB, 提交时间: 2025-02-05 09:25:46
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup1 = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans = [];
const path = [];
function dfs(i) {
if (i === n) {
ans.push([...path]);
return;
}
// 选 x
const x = nums[i];
path.push(x);
dfs(i + 1);
path.pop(); // 恢复现场
// 不选 x，那么后面所有等于 x 的数都不选
// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i++;
while (i < n && nums[i] === x) {
i++;
}
dfs(i);
}
dfs(0);
return ans;
};
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans = [];
const path = [];
function dfs(i) {
ans.push([...path]);
// 在 [i,n-1] 中选一个 nums[j]
// 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for (let j = i; j < n; j++) {
// 如果 j>i，说明 nums[j-1] 没有选
// 同方法一，所有等于 nums[j-1] 的数都不选
if (j > i && nums[j] === nums[j - 1]) {
continue;
}
path.push(nums[j]);
dfs(j + 1);
path.pop(); // 恢复现场
}
}
dfs(0);
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 4.3 MB, 提交时间: 2025-02-05 09:22:52
func subsetsWithDup(nums []int) (ans [][]int) {
slices.Sort(nums)
n := len(nums)
path := []int{}
var dfs func(int)
dfs = func(i int) {
ans = append(ans, slices.Clone(path))
// 在 [i,n-1] 中选一个 nums[j]
// 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for j := i; j < n; j++ {
// 如果 j>i，说明 nums[j-1] 没有选
// 同方法一，所有等于 nums[j-1] 的数都不选
if j > i && nums[j] == nums[j-1] {
continue
}
path = append(path, nums[j])
dfs(j + 1)
path = path[:len(path)-1] // 恢复现场
}
}
dfs(0)
return ans
}
// 选或不选
func subsetsWithDup2(nums []int) (ans [][]int) {
slices.Sort(nums)
n := len(nums)
path := []int{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(path))
return
}
// 选 x
x := nums[i]
path = append(path, x)
dfs(i + 1)
path = path[:len(path)-1] // 恢复现场
// 不选 x，跳过所有等于 x 的数
// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i++
for i < n && nums[i] == x {
i++
}
dfs(i)
}
dfs(0)
return ans
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 13.3 MB, 提交时间: 2025-02-05 09:21:54
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](this auto&& dfs, int i) -> void {
if (i == n) {
ans.push_back(path);
return;
}
// 选 x
int x = nums[i];
path.push_back(x);
dfs(i + 1);
path.pop_back(); // 恢复现场
// 不选 x，跳过所有等于 x 的数
// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i++;
while (i < n && nums[i] == x) {
i++;
}
dfs(i);
};
dfs(0);
return ans;
}
// 枚举选哪个
vector<vector<int>> subsetsWithDup2(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
vector<vector<int>> ans;
vector<int> path;
auto dfs = [&](this auto&& dfs, int i) -> void {
ans.push_back(path);
// 在 [i,n-1] 中选一个 nums[j]
// 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for (int j = i; j < n; j++) {
// 如果 j>i，说明 nums[j-1] 没有选
// 同方法一，所有等于 nums[j-1] 的数都不选
if (j > i && nums[j] == nums[j - 1]) {
continue;
}
path.push_back(nums[j]);
dfs(j + 1);
path.pop_back(); // 恢复现场
}
};
dfs(0);
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 42.6 MB, 提交时间: 2025-02-05 09:21:40
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(0, nums, ans, path);
return ans;
}
private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path) {
ans.add(new ArrayList<>(path));
// 在 [i,n-1] 中选一个 nums[j]
// 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for (int j = i; j < nums.length; j++) {
// 如果 j>i，说明 nums[j-1] 没有选
// 同方法一，所有等于 nums[j-1] 的数都不选
if (j > i && nums[j] == nums[j - 1]) {
continue;
}
path.add(nums[j]);
dfs(j + 1, nums, ans, path);
path.remove(path.size() - 1); // 恢复现场
}
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 42.6 MB, 提交时间: 2025-02-05 09:21:24
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(0, nums, ans, path);
return ans;
}
private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path) {
int n = nums.length;
if (i == n) {
ans.add(new ArrayList<>(path));
return;
}
// 选 x
int x = nums[i];
path.add(x);
dfs(i + 1, nums, ans, path);
path.remove(path.size() - 1); // 恢复现场
// 不选 x，跳过所有等于 x 的数
// 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i++;
while (i < n && nums[i] == x) {
i++;
}
dfs(i, nums, ans, path);
}
}
python3 解法, 执行用时: 0 ms, 内存消耗: 17.9 MB, 提交时间: 2025-02-05 09:19:55
class Solution:
# 选或不选，先排序
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
path = []
def dfs(i: int) -> None:
if i == n:
ans.append(path.copy()) # 也可以写 path[:]
return
# 选 x
x = nums[i]
path.append(x)
dfs(i + 1)
path.pop() # 恢复现场
# 不选 x，那么后面所有等于 x 的数都不选
# 如果不跳过这些数，会导致「选 x 不选 x'」和「不选 x 选 x'」这两种情况都会加到 ans 中，这就重复了
i += 1
while i < n and nums[i] == x:
i += 1
dfs(i)
dfs(0)
return ans
# 枚举选哪个
def subsetsWithDup2(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
path = []
def dfs(i: int) -> None:
ans.append(path.copy()) # 也可以写 path[:]
# 在 [i,n-1] 中选一个 nums[j]
# 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
for j in range(i, n):
# 如果 j>i，说明 nums[j-1] 没有选
# 同方法一，所有等于 nums[j-1] 的数都不选
if j > i and nums[j] == nums[j - 1]:
continue
path.append(nums[j])
dfs(j + 1)
path.pop() # 恢复现场
dfs(0)
return ans
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
}