calgorithmcombinatorics

How many ways can I choose numbers (repeatable) from a set that amount to the same sum?


For example, I have the following denominations

{5, 10, 20, 50}

The user input the amount they want to withdraw (e.g. 20), and the code will print out 4 because there are 4 ways to stack these bills to the sum of 20 (the maximum amount of bills is 5 and the order is irrelevant).

  1. 5, 5, 5, 5
  2. 5, 5, 10
  3. 10, 10
  4. 20

This is what my code looks like

#include <stdio.h>

#define DENOMINATIONS 4
#define MAX_BILLS 5

int denominations[DENOMINATIONS] = {5, 10, 20, 50};

int countWays(int amount, int index) {

    if (amount == 0) {
        return 1;
    }
    
    if (amount < 0 || index >= DENOMINATIONS) {
        return 0;
    }
    
    int ways = 0;
    
    for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
        ways += countWays(amount - denominations[index], index + 1);
    }
    
    return ways;
}

I thought it was okay, but the code doesn't work well with larger numbers such as 150 (where the expected result is 2 but the actual is 15) or 2700 (expected 0 but got 11)


Solution

  • At least these issues:

    Insufficient subtraction

    Subtract based on the number of bills used.

    // ways += countWays(amount - denominations[index], index + 1);
       ways += countWays(amount - i*denominations[index], index + 1);
    

    OK to match the amount.

    //for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
      for (int i = 0; i < MAX_BILLS && i * denominations[index] <= amount; i++) {
    

    Best to test failure first

    This test

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

    ... should be after

    if (amount < 0 || index >= DENOMINATIONS) {
            return 0;
        }
    

    ... to prevent an invalid index from being counted as a solution.

    Max number of bills needs clarity

    OP's code limit the bill count to 5 per denomination.

    If the total number of bills of all denominations is 5, then code needs to pass the bill count as part of countWays().

    int countWays(int amount, int index, int bills_allowed) {