Problem

  • Given a set of infinite coins
  • Find the number of ways to making change for a specific amount of money, without considering the order of the coins

Example

  • Input: given a set of infinite coins {2, 3, 1}. Find the number of ways to making change for 4
  • Expected output: 4
  • Explanation: those 4 ways are {1, 1, 1, 1}, {1, 1, 2}, {1, 3} and {2, 2}

Approach

  • To making change for a value j, need to use coins with value less than or equal to j

  • For each coin in the set c[i], calculate the ways of making change w[j] = w[j] + w[j - c[i]] with c[i] <= j <= target, w[0] = 1 is base case, w[target] is the final result

Implementation


Complexity

  • Time complexity: O(nm) with n is the change target, m is the number of coins
  • Space complexity: O(n) with n is the change target

References