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

Note: The solution set must not contain duplicate subsets.

Example 1:

Input: 1,2,3]

Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

from typing import List, Dict

class Solution:
    def subsetsHelper(self, nums: List[int], result: List[List[int]], arr: List[int], i: int) -> None:
        result.append(arr.copy())

        for j in range(i, len(nums)):
            arr.append(nums[j])
            self.subsetsHelper(nums, result, arr, j+1)
            arr.pop()

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.subsetsHelper(nums, result, [], 0)
        return result

Test Cases

test = Solution()
answer = test.subsets([1,2,3])
answer = list(answer)
answer.sort()
assert answer == [
    [],
    [1],
    [1,2],
    [1,2,3],
    [1,3],
    [2],
    [2,3],
    [3],
], answer
print('All Passed!')

Big O Analysis

Space Complexity: O(2^N)

Time Complexity: O(2^N)