78.-subsets.md

description
Back-tracking

78. Subsets

• Medium

• 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.

Analysis

Still, this is another example of backtracking problem. For each of the elements, there are two choices, add it to the current sequence or don't add it to the current sequence. Then the two extreme situations are 1. all of the elements are in the sequence 2.None of the elements is in the sequence. Since both those cases fits the definition of subsets, we don't have to consider any corner cases in our code.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        k=0
        ans=[]
        answer=[]
        self.helper(k,ans,answer,nums)
        return answer
        
    def helper(self,k,ans,answer,nums):
        if k==len(nums):
            answer.append(ans)
            return 
        self.helper(k+1,ans,answer,nums)
        self.helper(k+1,ans+[nums[k]],answer,nums)
        return