LC 78 - Subsets

Question

Given an integer array nums of unique elements, 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,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

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

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Links

Question here and solution here

Solution

concept

Standard backtrack algorithm. Take note the way we add the elements into the subsets in the include path, and then when we are backtracking we have to remove the element (i.e. choose to exclude current element). By design there will not be any duplicate. Also take note that since we are advancing the idx at every step, this means the same element is used only once.

code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        subset = []

        def dfs(idx):
            if idx >= len(nums):
                ans.append(subset.copy())
                return

            # include current element
            subset.append(nums[idx])
            dfs(idx + 1)

            # do not include current element
            subset.pop()
            dfs(idx + 1)

        dfs(0)

        return ans

Complexity

time: $O(n * 2^n)$
space: $O(n)$ extra space and $O(2^n)$