39. Combination Sum

# We don't need a visited set if we traverse the solution in a way that creates no repeated visits to the same combination
# ex. let candidates = [1, 2, 3, 4], target = 5
# possible combinations: (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 3), ...
# notice how there is no point visiting (1, 1, 2, 1) when we've already been at (1, 1, 1, 2)
# In general, we don't need to look at previous candidates when finding 'neighbors'
# So the problem structure is actually a tree (N-ary tree)
# We can use a "start" index in the backtrack function to indicate the smallest index to search from

# TC: O(N^(T/M + 1)) where N is num candidates, T is target, M is min element in candidates.
# Why? The height of the tree is T/M, since that's the longest combo we can form
# maxmal number of nodes in N-ary tree is n^(h + 1)

# SC: T/M, max number of recursions stacks we incur and also max len of combo

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []

        def backtrack(remain, combo, start):
            if not remain:
                results.append(combo.copy())
                return
            elif remain < 0:
                return

            for i in range(start, len(candidates)):
                combo.append(candidates[i])
                backtrack(remain - candidates[i], combo, i)
                combo.pop()

        backtrack(target, [], 0)
        return results