Given a list of coins[] representing different denominations, count all combinations of the coins to make a given value sum.

Hint

Imagine you have a set of coins and a target amount of money. You can either use a specific coin or not use it. If you use it, you reduce the amount you need to make change for. If you don't use it, you move on to the next coin. The result is sum of all possible combinations of using and not using each coin to find the total number of ways to reach the target amount.

# Python implementation

def count(coins, total):
  if (total < 0 or len(coins) <= 0):
    return 0

  if total == 0:
    return 1

  return count(coins, total - coins[0]) + count(coins[1:], total)

coins = [1, 2, 3]
total = 4

print(count(coins, total))

// Javascript implementation

function count(coins, sum) {
  if (sum < 0 || coins.length <= 0) {
    return 0;
  }

  if (sum === 0) {
    return 1;
  }

  return count(coins, sum - coins[0]) + count(coins.slice(1), sum);
}

const coins = [1, 2, 3];
const sum = 4;

console.log(count(coins, sum));

Find number of way to make coin change

Hint