Leetcode: Combination Sum

Combination Sum | LeetCode OJ

This is an extension of the coin change problem

Please refer to the coin change problem to understand how the algorithm works. Here we are keeping track of all the solutions for making change of an amount.

From the coin change post we know the following, when nth coin is added the number of ways to get amount m is addition of

1. Ways to make change without using nth coin. This is obtained from the left cell
2. Ways to make change with use of nth coin. This is obtained from the value n steps above in the same column

Now the combinations for change of m before adding the nth coin are already known to us. So we only need to add combinations using the nth coin.

Remarks:

1. Exponential time and space complexity as the number of solutions we need to store and compute rises exponentially

from collections import defaultdict

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        dp = defaultdict(int)
        solutions = defaultdict(list)
        dp[0] = 1
        solutions[0] = [[]]
        m = len(candidates)
        for i in range(0, m):
            for j in range(candidates[i], target + 1):
                dp[j] += dp[j - candidates[i]]
                for sol in solutions[j - candidates[i]]:
                    new_sol = []
                    new_sol.extend(sol)
                    new_sol.append(candidates[i])
                    solutions[j].append(new_sol)
        return solutions[target]