# LeetCode - Subsets II

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/subsets-ii.

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
``````

### Explanation

#### Backtracking

The approach for this problem is similar to our previous blog LeetCode Subsets. The only difference is we need to exclude duplicate elements here while generating the subset.

First, we will sort the nums array. We can either exclude the duplicate elements while recursively calling the subset generator function or we can mark the subset as a Set (Set is an abstract data type that can store unique values).

Let's check the algorithm first.

``````// subsetsWithDup(nums) function
- sort nums array sort(nums.begin(),nums.end())

- initialize vector<int> subset
set<vector<int>> result
vector<vector<int>> answer

- call util function subsetsUtil(nums, result, subset, 0)

- push set result in vector array
loop for(auto it:result)
answer.push_back(it)

- return answer

// subsetsUtil(nums, result, subset, index) function
- insert subset in result
result.insert(subset)

- loop for i = index; i < nums.size(); i++
- subset.push_back(nums[i])

- subsetsUtil(nums, result, subset, i + 1)

- subset.pop_back()
``````

Let's check out our solutions in C++, Golang, and Javascript. Note: In the C++ solution the subset is a Set, while in Golang and Javascript it's a normal array and we have ignored the duplicates.

#### C++ solution

``````class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<int> subset;
set<vector<int>> result;

subsetsUtil(nums, result, subset, 0);

vector<vector<int>> answer;

for(auto it:result){
answer.push_back(it);
}

return answer;
}

public:
void subsetsUtil(vector<int>& nums, set<vector<int>>& result, vector<int>& subset, int index) {
result.insert(subset);

for(int i = index; i < nums.size(); i++){
subset.push_back(nums[i]);

subsetsUtil(nums, result, subset, i + 1);

subset.pop_back();
}

return;
}
};``````

#### Golang solution

``````func subsetsUtils(nums, subset []int, result *[][]int) {
cp := make([]int, len(subset))
copy(cp, subset)

*result = append(*result, cp)

for i := 0; i < len(nums); i++ {
subsetsUtils(nums[i+1:], append(subset, nums[i]), result)

for ; i < len(nums)-1 && nums[i] == nums[i+1]; i++ {
}
}
}

func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)

var result [][]int
subset := make([]int, 0, len(nums))

subsetsUtils(nums, subset, &result)

return result
}``````

#### Javascript solution

``````var subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);

const result = [];

subsetsUtils(0, []);

return result;

function subsetsUtils (index, array) {
result.push([...array]);

for (let i = index; i < nums.length; i++) {
if (i > index && nums[i] == nums[i - 1]) {
continue;
}

array.push(nums[i]);
subsetsUtils(i + 1, array);
array.pop();
}
}
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: nums = [1, 2, 2]

Step 1: sort(nums.begin(),nums.end())
nums = [1, 2, 3]

Step 2: initialize vector<int> subset
set<vector<int>> result

Step 3: subsetsUtil(nums, result, subset, 0)

// in subsetsUtils function
Step 4: result.push_back(subset)
result.push_back([])

result = [[]]

loop for i = index, i < nums.size()
i = 0
0 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[0])
subset.push_back(1)

subset = [1]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[]], [1], 0 + 1)
subsetsUtil([1, 2, 2], [[]], [1], 1)

Step 5: result.push_back(subset)
result.push_back([1])

result = [[], [1]]

loop for i = index, i < nums.size()
i = 1
1 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[1])
subset.push_back(2)

subset = [1, 2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1]], [1, 2], 1 + 1)
subsetsUtil([1, 2, 2], [[], [1]], [1, 2], 2)

Step 6: result.push_back(subset)
result.push_back([1, 2])

result = [[], [1], [1, 2]]

loop for i = index, i < nums.size()
i = 2
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(2)

subset = [1, 2, 2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 2 + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 3)

Step 7: result.push_back(subset)
result.push_back([1, 2, 3])

result = [[], [1], [1, 2], [1, 2, 3]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 8: Here we backtrack to last line of Step 6 where
i = 2
subset = [1, 2, 2]

We execute the next line
subset.pop()

subset = [1, 2]

Step 9: We backtrack to last line of Step 5 where
i = 1
subset = [1, 2]

We execute the next line
subset.pop()

subset = [1]

Step 10: For loop continues where we execute
loop for i = index, i < nums.size()
i = 2
i < nums.size()
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(2)

subset = [1, 2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2], 2 + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2], 3)

Step 11: result.push_back(subset)
result.push_back([1, 2])

result = [[], [1], [1, 2], [1, 2, 2]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 12: Here we backtrack to last line of Step 3 where
i = 0
subset = [1]

We execute the next line
subset.pop()

subset = []

Step 13: For loop continues where we execute
loop for i = index, i < nums.size()
i = 1
i < nums.size()
1 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[1])
subset.push_back(2)

subset = [2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [2], 1 + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [2], 2)

Step 14: result.push_back(subset)
result.push_back([2])

result = [[], [1], [1, 2], [1, 2, 2], [1, 2], [2]]

loop for i = index, i < nums.size()
i = 2
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(2)

subset = [2, 2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2]], [2, 2], 2 + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2]], [2, 2], 3)

Step 15: result.push_back(subset)
result.push_back([2, 2])

result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 16: Here we backtrack to last line of Step 14 where
i = 2
subset = [2, 2]

We execute the next line
subset.pop()

subset = [2]

Step 17: Here we backtrack to last line of Step 13 where
i = 1
subset = [2]

We execute the next line
subset.pop()

subset = []

Step 18: For loop continues where we execute
loop for i = index, i < nums.size()
i = 2
i < nums.size()
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(2)

subset = [2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2], [2, 2]], [2], 2 + 1)
subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2], [2, 2]], [2], 3)

Step 19: result.push_back(subset)
result.push_back([2])

result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 20: We have no more stack entries left. We return to the main function.

Step 21: for(auto it:result){
answer.push_back(it);
}

We push result Set to answer Vector.

Step 22: return answer

So we return the answer as [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
``````
Share this post!