combination_sum.py

# source: https://leetcode.com/problems/combination-sum
# video: https://youtu.be/0Jt9_qKimCU

def combinationSum(candidates, target):
    dp = [[] for _ in range(target + 1)] # len(dp) = target + 1 b/c want to start with 0
    # intitialize with target = 0, must be empty
    dp[0].append([]) # start out as empty list, with sum total = 0

    # since combinations mean order doesn't matter, we should ensure we don't pass over 
    # parts already calculated ("old" ground)

    # loop through all candidates (ensures we only pass over "new" ground)
    for candidate in candidates: # O(n)
        # go through all targets in dp list and look up previous complimentary value solutions
        for value in range(candidate, target + 1): # ensures only seeing "new" ground # O(m)
            complimentary_value = value - candidate # get complimentary value
            prev_solutions = dp[complimentary_value] # get previous solutions (if any)

            # add candidate to previous solutions and append to current value in dp list 
            dp[value] += [prev_solution + [candidate] for prev_solution in prev_solutions] # O(n)
    return dp[target] # Time Complexity = O(n * (m * n)) ~= O(n*m)