class Solution:
  # cascading, at each step, add the number to all current subsets
  # If it's a list of list, make sure copy each time or else it will modify reference
  # def find_subsets(self, nums):
  #   subsets = [[]]
  #   #[1, 2, 3]
  #   for num in nums: 
  #     subsets_copy = subsets.copy() # O(n)
  #     for subset in subsets_copy: # O(2^n) (k start with 1 and grow until 2^n for n)
  #       new_subnet = subset.copy() # O(N)
  #       new_subnet.append(num)
  #       subsets.append(new_subnet)
  #   return subsets

  def find_subsets(self, nums):
    result_subsets = []
    self.backtrack(0, [], result_subsets, nums)
    return result_subsets
  # Backtracking solution, building each solution as we go down a tree of decision to build subset
  # backtrack(0, [], [], [1,2,3]) -> [[]]
  # ------backtrack(0, [1], [[]], nums) --> [[], [1]]
  # ----------backtrack(1, [1,2], [[], [1]], nums) ----> [] [1] [1,2]=> pop2
  # --------------backtrack(2, [1,2,3], result, nums) ----> [] [1] [1,2] [1,2,3] => pop(3)
  # ----------backtrack(1, [1,3], result, nums) ----> [] [1] [1,2] [1,2,3] [1,3] => pop(3) 
  # ------backtrack()
  def backtrack(self, curr_index: int, curr_subset: List[int], result_subsets: List[List[int]], nums: List[int]):
    result_subsets.append(curr_subset[:])
    for index in range(curr_index, len(nums)):
      curr_subset.append(nums[index])
      self.backtrack(index+1, curr_subset, result_subsets, nums)
      curr_subset.pop()