LC78 Subset

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """tc O(N*2^N)  sc O(N*2^N)
        """
        res = []
        size = len(nums)
        def dfs(start, path):
            res.append(path.copy())  # or path[:]
            for i in range(start, size):
                path.append(nums[i])
                dfs(i+1, path)   # if not using path.copy(), can do dfs(i+1, path + [nums[i]]) and remove pop operation 
                path.pop()
        dfs(0,[])
        return res 

class Solution:
    def subsets(self, A: List[int]) -> List[List[int]]:
        """tc O(N*2^N)  sc O(N*2^N)
            cascading
        """
        res = [[]]
        for a in A:
            new_res = []
            for each in res:
                tmp = each[:]
                tmp.append(a)
                new_res.append(tmp)
            for ll in new_res:
                res.append(ll)
        return res