# 90. Subsets II

## 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 searching for subsets starting from the $i$-th element. The execution logic of the function $dfs(i)$ is as follows:

If $i \geq n$, it means that all elements have been searched, and the current subset is added to the answer array, and the recursion ends.

If $i < n$, add the $i$-th element to the subset, execute $dfs(i + 1)$, and then remove the $i$-th element from the subset. Next, we judge whether the $i$-th element is the same as the next element. If it is the same, we loop to skip this element until we find the first element that is different from the $i$-th element, and execute $dfs(i + 1)$.

Finally, we only need to call $dfs(0)$ and return the answer array.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

Take the example [1 2 2] in the title for analysis. According to the analysis in Subsets before, when the first 2 is processed, the subsets at this time are [], [1], [2], [1, 2], and when processing the second 2 at this time, if you add 2 directly after [] and [1], there will be duplication, so you can only add 2 after the last two subsets generated by the previous loop.

We use last to record the last processed number, and then determine whether the current number is the same as the above.

• If it is different, the loop will continue from 0 to the number of the current subset.
• If the same, then The number of new subsets minus the number of subsets in the previous loop is used as the starting point to loop, so that there will be no duplication

My solving process:

nums = [1,2,2,2]
[],1,	2,12,	2,12,22,122,	2,12,22,122,22,122,222,1222


from above, every time the new add is doubled, count: 1,2,4,8 so, the 1st half is duplicated, and 2nd half is NOT duplicated so, when going into a new loop, append duplicated num to ONLY 2nd half elements

then:

[],1


append 2, not duplicated, append as normal:

[],1,	2, 12


append 2, same as previous 2, then append last 2 elements - “2,12”

[],1,	2, 12,		22,122


append 2, same as previous 2, then append last 2 elements - “22,122”

[],1,	2, 12,		22,122,		222,1222


append 2, same as previous 2, then append last 2 elements - “222,1222”

[],1,	2, 12,		22,122,		222,1222,		2222,12222


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 of $[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 to select $nums[i]$, and $0$ means not to select $nums[i]$. Note that if the $i - 1$ bit of $mask$ is $0$, and $nums[i] = nums[i - 1]$, it means that in the current enumerated scheme, the $i$-th element and the $i - 1$-th element are the same. To avoid repetition, we skip this situation. Otherwise, we add the subset corresponding to $mask$ to the answer array.

After the enumeration ends, we return the answer array.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

• class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
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;
}
}
}
if (ok) {
}
}
return ans;
}
}

• class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ans;
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;
}
};

• class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(u, t):
ans.append(t[:]) # or, t.copy()
for i in range(u, len(nums)):
# also good for [1,5,5], second '5' will be skipped here if
# but second '5' is always covered, because i==u when ans=[1,5] and i=2
if i != u and nums[i] == nums[i - 1]:
continue
t.append(nums[i])
dfs(i + 1, t)
t.pop()

ans = []
nums.sort()
dfs(0, [])
return ans

# iteration
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if not nums:
return [[]]

nums.sort()  # Sorting is necessary to handle duplicates.
result = [[]]
start_idx = 0  # Start index for the new subsets
new_subsets_size = 0

for i in range(len(nums)):
size = len(result)
# If the current number is the same as the previous one,
# we only want to extend the subsets added in the previous iteration.
if i > 0 and nums[i] == nums[i - 1]:
start_idx = size - new_subsets_size
else:
start_idx = 0

new_subsets_size = 0  # Reset the size of newly created subsets
for j in range(start_idx, size):
current_subset = result[j] + [nums[i]]
result.append(current_subset)
new_subsets_size += 1

return result

############

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


• func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
t := []int{}
ok := true
for i := 0; i < n; i++ {
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
}

• function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans: number[][] = [];
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;
}


• 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
}
}