[LeetCode] 78. Subsets

Problem : https://leetcode.com/problems/subsets/

This looks like a follow-up problem of 77. Combinations

Use the same approach to generate the combinations with max length from 0 to len(nums).

Backtracking Solution:

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtracking(start, partial, maxLen):
            if len(partial) == maxLen:
                result.append(partial)
                
            
            for i in range(start, len(nums)):
                # pick nums[i]
                backtracking(i+1, partial + [nums[i]], maxLen)
                # not pick nums[i]
        
        
        # generate combination with max length from 0 to len(nums)
        for i in range(len(nums) + 1):
            backtracking(0, [], i)
        
        return result

DFS Solution :

Consider the code is traversing a tree. On each node it has 2 options to pick or not pick the number on this node.

Time Complexity = O ( N ** 2 * N ).   

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        
        def dfs(start, partial):
            if start == len(nums):
                result.append(partial)
                return
            
            # not pick nums[start]
            dfs(start + 1, partial)
            
            # pick nums[start]
            dfs(start + 1, partial + [nums[start]])
            
        dfs(0, [])
        
        return result

Cascading Solution:

Get new subsets by append current number to the subsets generated by the last step.

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = [[]]
        
        for n in nums:
            for i in range(len(result)):
                # append current number to subsets 
                # generated by last step
                result.append(result[i] + [n])
        
        return result