[link](https://leetcode.com/problems/subsets-ii/)

---

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

---

Initialize an empty list res to store the final list of subsets and an empty list subset to store the current subset being constructed. Sort the input nums list in ascending order. This is done to handle duplicate elements efficiently. Define a recursive DFS function dfs(i, nums, res, subset) that takes the current index i, the nums list, the res list to store subsets, and the subset list to store the current subset.

In the DFS function, first check if i is beyond the length of nums. If so, it means we have processed all the elements, and the current subset is a valid subset. So, add a copy of subset to res, and return to backtrack. Add the current element nums[i] to the subset and call the DFS function recursively with i+1 to process the next element. After the recursive call, remove the last element from subset, effectively backtracking and exploring other possibilities. Check for duplicate elements in the nums list. While i+1 is within the bounds of the list and the current element nums[i] is the same as the next element nums[i+1], increment i to skip over duplicates.

Call the DFS function recursively with the new value of i+1 to explore other subsets without duplicates. Call the DFS function initially with i=0 to start constructing the subsets. Return the final list of subsets res.

#### Solution 1

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res, subset = [], []
        nums.sort()
        
        def dfs(i, nums, res, subset):
            if i >= len(nums):
                res.append(subset.copy())
                return 
            
            subset.append(nums[i])
            dfs(i + 1, nums, res, subset)
            subset.pop()
            
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            dfs(i + 1, nums, res, subset)

        dfs(0, nums, res, subset)
        return res
        

O(T): O(2^n)
O(S): O(2^n)