# Question

Formatted question description: https://leetcode.ca/all/90.html

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

# Algorithm

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


# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets_II {

public static void main(String[] args) {
Subsets_II out = new Subsets_II();
Solution s = out.new Solution();

for (List<Integer> each : s.subsetsWithDup(new int[]{1, 1})) {
System.out.println(each.toString());
}
}

class Solution_better {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
backtrack(0, nums, new ArrayList<>(), res);
return res;
}

private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) { // key is i>start, so it covers input=[1,5,5]
continue;
}
backtrack(i+1, nums, path, res);
path.remove(path.size() - 1);
}
}
}

class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if (nums == null || nums.length == 0) {
return list;
}

Arrays.sort(nums); // requirement: non-descending order

// prepare, add empty one to start looping then.
// @note: I forgot empty
ArrayList<Integer> empty = new ArrayList<>();

int prevIndex = 0;

for (int i = 0; i < nums.length; i++) {

int start = (i > 0 && nums[i] == nums[i - 1]) ? prevIndex : 0;

for (int j = start; j < list.size(); j++) {
List<Integer> each = list.get(j);
ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy

}

prevIndex = list.size();
}

return list;
}
}
}

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

class Solution {
private List<List<Integer>> ans;
private int[] nums;

public List<List<Integer>> subsetsWithDup(int[] nums) {
ans = new ArrayList<>();
Arrays.sort(nums);
this.nums = nums;
dfs(0, new ArrayList<>());
return ans;
}

private void dfs(int u, List<Integer> t) {
for (int i = u; i < nums.length; ++i) {
if (i != u && nums[i] == nums[i - 1]) {
continue;
}
dfs(i + 1, t);
t.remove(t.size() - 1);
}
}
}

• // OJ: https://leetcode.com/problems/subsets-ii/
// Time: O(2^N * N^2)
// Space: O(2^N * N)
class Solution {
set<vector<int>> s;
vector<int> tmp;
void dfs(vector<int> &A, int i) {
if (i == A.size()) {
s.insert(tmp);
return;
}
dfs(A, i + 1);
tmp.push_back(A[i]);
dfs(A, i + 1);
tmp.pop_back();
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& A) {
sort(begin(A), end(A));
dfs(A, 0);
return vector<vector<int>>(begin(s), end(s));
}
};

• 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]]:
nums.sort() # requirement: non-descending order
res = [[]]
prev_index = 0

for i in range(len(nums)):

start = prev_index if (i > 0 and nums[i] == nums[i - 1]) else 0

for j in range(start, len(res)):
each = res[j]
new_one = each.copy() # deep copy

prev_index = len(res)

return res

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

class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

def dfs(start, nums, path, res, visited):
res.append(path + [])

for i in range(start, len(nums)):
if start != i and nums[i] == nums[i - 1]:
continue
if i not in visited:
visited[i] = 1
path.append(nums[i])
dfs(i + 1, nums, path, res, visited)
path.pop()
del visited[i]

nums.sort()
res = []
visited = {}
dfs(0, nums, [], res, visited)
return res


• func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
var ans [][]int
var dfs func(u int, t []int)
dfs = func(u int, t []int) {
ans = append(ans, append([]int(nil), t...))
for i := u; i < len(nums); i++ {
if i != u && nums[i] == nums[i-1] {
continue
}
t = append(t, nums[i])
dfs(i+1, t)
t = t[:len(t)-1]
}
}
var t []int
dfs(0, t)
return ans
}

• function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const t: number[] = [];
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...t]);
return;
}
t.push(nums[i]);
dfs(i + 1);
const num = t.pop();
while (i < n && nums[i] == num) {
i++;
}
dfs(i);
};
dfs(0);
return res;
}


• impl Solution {
fn dfs(mut i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
let n = nums.len();
if i == n {
res.push(t.clone());
return;
}
t.push(nums[i]);
Self::dfs(i + 1, t, res, nums);
let num = t.pop().unwrap();
while i < n && num == nums[i] {
i += 1;
}
Self::dfs(i, t, res, nums);
}

pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let mut res = Vec::new();
Self::dfs(0, &mut Vec::new(), &mut res, &nums);
res
}
}