Subsets - Backtracking / Additional Practices

Problems
21

the 2nd solution doesn’t traverse all the include & excludes, e.g. at node 2 from the root, you only go forward to 3

22

add a print at the top of dfs shows 8 calls.

23

Doesn’t the runtime seem factorial O(n!) for the alternative solution or was the runtime given for the first solution?

24

a nice way of doing this


def subsets(nums: List[int]) -> List[List[int]]:
    
    result = []
    
    def dfs(index, path):
        
        if index == len(nums):
            result.append(path[:])
            result.append(path[:-1])
            return
            
        for i in range(index, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
            
    dfs(0, []) 
    return result