Leetcode 90. Subsets II

Problem

Leetcode 90 - Subsets II

Example:

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

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

Approach

Similar to the subset question, we can get the subset by first sorting the array, then running DFS.

Here is the Python code for the solution:

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def dfs(i, arr):
            if i == len(nums):
                res.append(arr.copy())
                return
            if arr in res:
                return

            dfs(i+1, arr+[nums[i]])
            dfs(i+1, arr)

        dfs(0, [])
        return res     

Time Complexity and Space Complexity

Time Complexity: $O(2^n)$

Space Complexity: $O(n)$