Description
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
Solutions
Solution 1: Sorting + DFS
We can first sort the array nums to facilitate deduplication.
Then, we design a function dfs(i), which represents the current search for subsets starting from the i-th element. The execution logic of the function dfs(i) is as follows:
If i ≥ n, it means all elements have been searched, add the current subset to the answer array, and end the recursion.
If i < n, add the i-th element to the subset, execute dfs(i + 1), then remove the i-th element from the subset. Next, we check if the i-th element is the same as the next element. If they are the same, skip the element in a loop until we find the first element different from the i-th element, then execute dfs(i + 1).
Finally, we only need to call dfs(0) and return the answer array.
The time complexity is O(n × 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i == len(nums):
ans.append(t[:])
return
t.append(nums[i])
dfs(i + 1)
x = t.pop()
while i + 1 < len(nums) and nums[i + 1] == x:
i += 1
dfs(i + 1)
nums.sort()
ans = []
t = []
dfs(0)
return ans(code-box)
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i >= nums.length) {
ans.add(new ArrayList<>(t));
return;
}
t.add(nums[i]);
dfs(i + 1);
int x = t.remove(t.size() - 1);
while (i + 1 < nums.length && nums[i + 1] == x) {
++i;
}
dfs(i + 1);
}
}(code-box)
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
ranges::sort(nums);
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
auto dfs = [&](this auto&& dfs, int i) {
if (i >= n) {
ans.push_back(t);
return;
}
t.push_back(nums[i]);
dfs(i + 1);
t.pop_back();
while (i + 1 < n && nums[i + 1] == nums[i]) {
++i;
}
dfs(i + 1);
};
dfs(0);
return ans;
}
};(code-box)
func subsetsWithDup(nums []int) (ans [][]int) {
slices.Sort(nums)
n := len(nums)
t := []int{}
var dfs func(int)
dfs = func(i int) {
if i >= n {
ans = append(ans, slices.Clone(t))
return
}
t = append(t, nums[i])
dfs(i + 1)
t = t[:len(t)-1]
for i+1 < n && nums[i+1] == nums[i] {
i++
}
dfs(i + 1)
}
dfs(0)
return
}(code-box)
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const t: number[] = [];
const ans: number[][] = [];
const dfs = (i: number): void => {
if (i >= n) {
ans.push([...t]);
return;
}
t.push(nums[i]);
dfs(i + 1);
t.pop();
while (i + 1 < n && nums[i] === nums[i + 1]) {
i++;
}
dfs(i + 1);
};
dfs(0);
return ans;
}(code-box)
impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let mut ans = Vec::new();
let mut t = Vec::new();
fn dfs(i: usize, nums: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if i >= nums.len() {
ans.push(t.clone());
return;
}
t.push(nums[i]);
dfs(i + 1, nums, t, ans);
t.pop();
let mut i = i;
while i + 1 < nums.len() && nums[i + 1] == nums[i] {
i += 1;
}
dfs(i + 1, nums, t, ans);
}
dfs(0, &nums, &mut t, &mut ans);
ans
}
}(code-box)
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function (nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const t = [];
const ans = [];
const dfs = i => {
if (i >= n) {
ans.push([...t]);
return;
}
t.push(nums[i]);
dfs(i + 1);
t.pop();
while (i + 1 < n && nums[i] === nums[i + 1]) {
i++;
}
dfs(i + 1);
};
dfs(0);
return ans;
};(code-box)
public class Solution {
private IList<IList<int>> ans = new List<IList<int>>();
private IList<int> t = new List<int>();
private int[] nums;
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
this.nums = nums;
Dfs(0);
return ans;
}
private void Dfs(int i) {
if (i >= nums.Length) {
ans.Add(new List<int>(t));
return;
}
t.Add(nums[i]);
Dfs(i + 1);
t.RemoveAt(t.Count - 1);
while (i + 1 < nums.Length && nums[i + 1] == nums[i]) {
++i;
}
Dfs(i + 1);
}
}(code-box)
Solution 2: Sorting + Binary Enumeration
Similar to Solution 1, we first sort the array nums to facilitate deduplication.
Next, we enumerate a binary number mask in the range [0, 2^n), where the binary representation of mask is an n-bit bit string. If the i-th bit of mask is 1, it means selecting nums[i], and 0 means not selecting nums[i]. Note that if the (i - 1)-th bit of mask is 0 and nums[i] = nums[i - 1], it means that the i-th element is the same as the (i - 1)-th element in the current enumeration scheme. To avoid duplication, we skip this case. Otherwise, we add the subset corresponding to mask to the answer array.
After the enumeration, we return the answer array.
The time complexity is O(n × 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for mask in range(1 << n):
ok = True
t = []
for i in range(n):
if mask >> i & 1:
if i and (mask >> (i - 1) & 1) == 0 and nums[i] == nums[i - 1]:
ok = False
break
t.append(nums[i])
if ok:
ans.append(t)
return ans(code-box)
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for (int mask = 0; mask < 1 << n; ++mask) {
List<Integer> t = new ArrayList<>();
boolean ok = true;
for (int i = 0; i < n; ++i) {
if ((mask >> i & 1) == 1) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
ok = false;
break;
}
t.add(nums[i]);
}
}
if (ok) {
ans.add(t);
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
vector<vector<int>> ans;
for (int mask = 0; mask < 1 << n; ++mask) {
vector<int> t;
bool ok = true;
for (int i = 0; i < n; ++i) {
if ((mask >> i & 1) == 1) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
ok = false;
break;
}
t.push_back(nums[i]);
}
}
if (ok) {
ans.push_back(t);
}
}
return ans;
}
};(code-box)
func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
ok := true
for i := 0; i < n; i++ {
if mask>>i&1 == 1 {
if i > 0 && mask>>(i-1)&1 == 0 && nums[i] == nums[i-1] {
ok = false
break
}
t = append(t, nums[i])
}
}
if ok {
ans = append(ans, t)
}
}
return
}(code-box)
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans: number[][] = [];
for (let mask = 0; mask < 1 << n; ++mask) {
const t: number[] = [];
let ok: boolean = true;
for (let i = 0; i < n; ++i) {
if (((mask >> i) & 1) === 1) {
if (i && ((mask >> (i - 1)) & 1) === 0 && nums[i] === nums[i - 1]) {
ok = false;
break;
}
t.push(nums[i]);
}
}
if (ok) {
ans.push(t);
}
}
return ans;
}(code-box)
impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut ans = Vec::new();
for mask in 0..1 << n {
let mut t = Vec::new();
let mut ok = true;
for i in 0..n {
if ((mask >> i) & 1) == 1 {
if i > 0 && ((mask >> (i - 1)) & 1) == 0 && nums[i] == nums[i - 1] {
ok = false;
break;
}
t.push(nums[i]);
}
}
if ok {
ans.push(t);
}
}
ans
}
}(code-box)
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function (nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans = [];
for (let mask = 0; mask < 1 << n; ++mask) {
const t = [];
let ok = true;
for (let i = 0; i < n; ++i) {
if (((mask >> i) & 1) === 1) {
if (i && ((mask >> (i - 1)) & 1) === 0 && nums[i] === nums[i - 1]) {
ok = false;
break;
}
t.push(nums[i]);
}
}
if (ok) {
ans.push(t);
}
}
return ans;
};(code-box)
public class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
IList<IList<int>> ans = new List<IList<int>>();
for (int mask = 0; mask < 1 << n; ++mask) {
IList<int> t = new List<int>();
bool ok = true;
for (int i = 0; i < n; ++i) {
if ((mask >> i & 1) == 1) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
ok = false;
break;
}
t.Add(nums[i]);
}
}
if (ok) {
ans.Add(t);
}
}
return ans;
}
}(code-box)
