Leetcode Problem 78 Subsets.txt

78. Subsets
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],
  []
]

Hint to solve: Use recursion with backtracking(popping the elements)

class Solution:
    
    def generateSubsetsRecursive(self, currentIndex, currentSubset, nums):
        #print('currentIndex: ', currentIndex, ' currentSubset', currentSubset)
        temp = currentSubset.copy()
        self.result.append(temp)
        
        for i in range(currentIndex, len(nums)):
            currentSubset.append(nums[i])
            self.generateSubsetsRecursive(i+1, currentSubset, nums)
            currentSubset.pop()
    
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        self.result = []
        self.generateSubsetsRecursive(0,[],nums)
        return self.result