LC 0078 0090 [M] [M] Subsets I II - ALawliet/algorithms GitHub Wiki

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def branch(i, path):
            if i == len(nums):
                res.append(path)
            else:
                branch(i + 1, path)             # exclude
                branch(i + 1, path + [nums[i]]) # include
            
        res = []
        branch(0, [])
        return res

time:
each digit we have 2 decisions, so the branching factor is 2, depth of tree is n number of digits, so 2^n
O(2^n)

space:
how many possible strings 2^n
immutable data structure n^2 creating a new string each level
O(2^n*n + n^2)

THIS 2ND METHOD WITH SKIP POINTERS IS BETTER TO LEARN BECAUSE MORE ADAPTABLE TO OTHER PROBLEMS AND DOES NOT TLE

looks more like a DFS like this:

# Subsets
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(start, path):
            res.append(path)
            for i in range(start, len(nums)):
                dfs(i + 1, path + [nums[i]])
        
        res = []
        dfs(0, [])
        return res

# Subsets II
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # new

        def dfs(start, path):
            res.append(path)
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i-1]: continue # new
                dfs(i + 1, path + [nums[i]])
        
        res = []
        dfs(0, [])
        return res

why does this level cache require sorted whereas permutations does not? draw the trees

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        nums.sort()

        def dfs(path, nums):
            self.res.append(path)
            dup = set() # sorted level cache
            for i in range(len(nums)):
                if not nums[i] in dup:
                    dfs(path+[nums[i]], nums[i+1:])
                    dup.add(nums[i])

        dfs([], nums)   
        return self.res

---

iterative

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        subsets.append([])
        for i in range(len(nums)):
            for j in range(len(subsets)):
                new_subset = subsets[j].copy()
                new_subset.append(nums[i])
                subsets.append(new_subset)
        return subsets

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        subsets = []
        subsets.append([])
        s, e = 0, 0
        for i in range(len(nums)):
            s = 0
            if i > 0 and nums[i] == nums[i-1]:
                s = e+1
            e = len(subsets) - 1
            for j in range(s, e+1):
                new_subset = subsets[j].copy()
                new_subset.append(nums[i])
                subsets.append(new_subset)
        return subsets