78_Subsets

[Medium][Backtracking]

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]

Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

Idea:

• There are $2^n$ subsets in total. Because each integer can be included or not.

• For each integer, use recursion to get subsets for the two possibilities:

  1. the subset includes the integer

  2. the subset doesn't include the integer

• For storing each solution, there are two ways:

  1. initialize a list called sol, update the elements when we progress.

  2. In the helper function, set a parameter called selected__so__far, which includes all the selected integers. Update this parameter when we progress.

Time Complexity: $O(n 2^n)$ there are $2^n$ paths in the tree

Space Complexity: $O(n 2^n)$ for the output

Code 1: use a list to update current solution

def subsets(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    def helper(i):
        # i is the position of integer we are handling
        if i == len(nums):
            output.append(list(sol))
            return 

        # case when nums[i] is not in the subset
        helper(i + 1)

        # case when nums[i] is in the subset
        sol.append(nums[i])
        helper(i + 1)
        sol.pop()

    output, sol = [], []
    helper(0)
    return output

Code 2: use a parameter in the helper function to store current solution

def subsets(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    def helper(to_be_selected, selected_so_far):
        # to_be_selected is the position of integer we are handling
        if to_be_selected == len(nums):
            output.append(list(selected_so_far))
            return 

        # case when nums[to_be_selected] is not in the subset
        helper(to_be_selected + 1, selected_so_far)

        # case when nums[to_be_selected] is in the subset
        helper(to_be_selected + 1, selected_so_far + [nums[to_be_selected]])

    output = []
    helper(0, [])
    return output

Solution 2: Mit Manipulation