Solution algorithm and thought process

  • 0

    One of the first thing to do about a problem like this is to try to construct a recursive solution (without worrying about optimality). That is, try to break it down into smaller sub-problems.

    The correct recursive solution to this problem is not very obvious, because enumerating combinations is not very straightforward. So first, instead of combinations, let's construct a recursive solution enumerating permutations of coins that add up to amount. (In other words, "How many possible sequences of coins exist that add up to amount?")

    Counting Valid Permutations

    Let's construct a (recursive) function that returns the number of possible coin-sequences given an amount and possible coin choices. At each step, for each possible coin choice, we call the function recursively with the reduced amount, and return the sum of all recursive calls. Terminating conditions: return 1 if amount == 0, or return 0 if amount < 0.

    def permutations(amount, coins):
        if amount < 0:
            return 0
        elif amount == 0:
            return 1
        sum = 0
        for coin in coins:
            sum += permutations(amount - coin, coins)
        return sum

    This has an exponential time complexity of O(m^n) where m is the number of coins and n is the amount.

    From Permutations to Combinations

    Let's take an example: amount = 12, coins = [1,2,5]. When these values are passed to the above permutations function, a tree of recursive calls are made where each path down the tree indicate a particular sequence of coins.

    1/   |2   \5
    11   10    7
    /|\  /|\  /|\
    ...  ...  ...

    Sequences such as 1 5 2 2 1 1 or 5 1 5 5 or 2 2 2 1 2 2 2 are all included in that tree.

    One valid way to enumerate combinations, is to constrain sequences to be only of the form 1 1 1 2 2 5 or 1 5 5 5 or 1 2 2 2 2 2 2 (i.e. 1s 2s 5s). Once this key observation is made, the recursive solution is fairly easy to construct.

    def combinations(amount, coins):
        if amount < 0:
            return 0
        elif amount == 0:
            return 1
        if len(coins) == 0:
            return 0
        # use the first coin
        sum = combinations(amount - coins[0], coins)
        # stop using the first coin
        sum += combinations(amount, coins[1:])
        return sum

    That's it! That's our recursive solution to the problem with a time complexity of O(2^n).

    Sidenote: The space complexity is also exponential for the above program because a copy of coins with one element fewer is created in each call. But that copy can be easily avoided by having an additional argument indicating offset index in coins.

    Dynamic Programming

    When there are large overlaps in the tree of recursive calls (i.e. if many duplicate function calls having identical arguments are made), then storing the results of those intermediate calls and reusing them as needed will most definitely save time. This technique is called Dynamic Programming or Dynamic Optimization ("dynamic" as in "at runtime").

    As a warm up, let's rewrite our permutations function using Dynamic Programming. First we note that among the arguments, amount varies from its initial value all the way till zero (or slightly negative) as we recurse deeper, while coins remain the same. So we just need to create a 1-D array having a length of (initial) amount + 1 whose ith element stores the result of permutations(i, coins). This array will be populated bottom-up, that is, from the base case (zero amount) and up till we reach the target amount.

    def permutations_dp(amount, coins):
        results = []
        results.append(1)  # case when amount is 0
        for a in range(amount + 1):  # a from 0 to amount (incl)
            for coin in coins:
                if a - coin >= 0:
                    results[a] += results[a - coin]
        return results[amount]

    This has a time complexity of O(mn) and space complexity of O(n).

    Below is a straightforward DP rewrite of our combinations function.

    def combinations_dp(amount, coins):
        results = []
        clen1 = len(coins) + 1
        for a in range(1, amount + 1):
            for ci in reversed(range(clen1-1)):
                if a - coins[ci] >= 0:
                    results[a][ci] = results[a - coins[ci]][ci]
                results[a][ci] += results[a][ci+1]
        return results[amount][0]

    This has a time and space complexity of O(mn), which can still be optimized for space.

    Observe that, in column i, we only need the last coins[i] values to calculate the values in future rows.

    def combinations_dp(self, amount, coins):
        clen = len(coins)
        if clen == 0:
            return 1 if amount == 0 else 0
        results = []
        for coin in coins:
            results.append([1] + [0]*(coin - 1))
        for a in range(1, amount + 1):
            for ci in reversed(range(clen - 1)):
                results[ci][a % coins[ci]] += results[ci+1][a % coins[ci+1]]
        return results[0][amount%coins[0]]

    Now the space-complexity is O(m min(k, n)) where k is the size of the biggest coin.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.