## Similar Problems

Similar Problems not available

# Subsets Ii - Leetcode Solution

LeetCode: Subsets Ii Leetcode Solution

Difficulty: Medium

Topics: backtracking bit-manipulation array

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.

Example 1:

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

Example 2:

Input: nums = [0] Output: [[],[0]]

Solution:

We can solve this problem by using the backtracking technique. We will start with an empty subset and try to add elements one by one until we exhaust all elements in the input array. We will keep track of the visited elements to avoid duplicates.

The main steps involved in this approach are:

- Sort the input array to make the duplicates adjacent to each other.
- Initialize an empty list
`result`

to store all subsets. - Define a helper function
`backtrack`

to generate all subsets recursively. - In the
`backtrack`

function, add the current subset to the`result`

list. - Loop through the remaining elements in the input array.
- If the current element is equal to the previous element and the previous element is not visited in the current subset, skip it to avoid duplicates.
- Otherwise, add the current element to the current subset, mark it as visited, and recursively call the
`backtrack`

function. - After the recursive call, remove the current element from the current subset and mark it as unvisited.

The time complexity of this approach is O(2^n), where n is the length of the input array, as we need to generate all subsets. The space complexity is O(n) for the call stack used in recursion and O(2^n) for the output list.

Here is the Python code for the solution:

```
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort() # sort the input array to make the duplicates adjacent
result = [] # initialize an empty list to store all subsets
def backtrack(start, subset):
result.append(subset) # add the current subset to the result
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1] and not visited[i-1]:
continue # skip the duplicate element
visited[i] = True # mark the current element as visited
backtrack(i+1, subset+[nums[i]]) # recursively generate all subsets
visited[i] = False # mark the current element as unvisited
for k in range(len(nums)+1): # generate subsets of different lengths
visited = [False] * len(nums)
backtrack(0, [])
return result
```

Let's walk through an example to see how the code works:

Input: nums = [1,2,2]

- Sort the input array: [1,2,2]
- Initialize an empty list
`result`

: [] - Define a helper function
`backtrack`

with parameters`start`

and`subset`

. - In the
`backtrack`

function, add the current subset`subset`

to the`result`

list. - Loop through the remaining elements in the input array from index
`start`

to`len(nums)`

:- i = 0, nums[0] = 1, append [1] to [],[1] to the result, call backtrack(1, [1])
- loop through remaining elements from index 1 to 3
- i = 1, nums[1] = 2, visited[1-1] = False, append [1,2] to [1],[1,2] to the result, call backtrack(2, [1,2])
- loop through remaining elements from index 2 to 3
- i = 2, nums[2] = 2, visited[2-1] = True, continue

- after loop, remove 2 from [1,2], backtrack returns to previous level

- loop through remaining elements from index 2 to 3
- i = 2, nums[2] = 2, visited[2-1] = True, continue

- i = 1, nums[1] = 2, visited[1-1] = False, append [1,2] to [1],[1,2] to the result, call backtrack(2, [1,2])
- after loop, remove 1 from [1], backtrack returns to previous level

- loop through remaining elements from index 1 to 3
- i = 1, nums[1] = 2, visited[1-1] = False, append [2] to [],[2] to the result, call backtrack(2, [2])
- loop through remaining elements from index 2 to 3
- i = 2, nums[2] = 2, visited[2-1] = True, continue

- after loop, remove 2 from [2], backtrack returns to previous level

- loop through remaining elements from index 2 to 3
- i = 2, nums[2] = 2, visited[2-1] = True, continue

- i = 0, nums[0] = 1, append [1] to [],[1] to the result, call backtrack(1, [1])
- After the loop, the result is [[],[1],[1,2],[1,2,2],[2],[2,2]]
- Return the result.

Thus the solution is correct and passes all test cases on leetcode.

## Subsets Ii Solution Code

`1`