Recursive method to count the number of combinations

Question

this is a java code that recursively counts the number of payments in specific coins (ex. 1, 2, 5, 20, 50 etc.). I have tried to figure out how it works but can't seem to get it. Could somebody please be so kind and explain the math and logic behind the code and how this recursion works? I would really appreciate it.

    // Returns the count of ways we can sum  S[0...m-1] coins to get sum n
int count( int S[], int m, int n ){

    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Answer 1

The method works like this:

1. First statements are the stopping conditions for the current recursion (without these for all cases then you end up with an infinite loop which ultimately end in a StackOverFlow)

2. The final line is where the calculation occurs. Each of the statements is reducing the problem into smaller chunks by:

   • count( S, m - 1, n ) reduces the number of coins (m-1) which excludes the last coin in the next recursive call to
   • count( S, m, n-S[m-1]) uses the last coin in the array and reduces the sum that is need to reach by the value of that coin

Consider this small example:

S[] = {1,2)    // We have a 1 and 2 cent coin
m   = S.length // Consider all possibilities  ( = 2)
n   = 3        // How many ways can we make 3c
               // Obviously with: 1x1c + 1x2c
               //            and: 3x1c

The recursion as a tree; left branch = count( S, m - 1, n ), right branch = count( S, m, n-S[m-1]):

                                  m=2;n=3
                                 /        \
                          m=1;n=3          m=2;n=1
                         /       \       /     \
                  m=0;n=3    m=1;n=2   m=1;n=1  m=2;n=-1
                            /     \     /     \
                     m=0;n=2  m=1;n=1 m=0;n=1  m=1;n=0
                             /     \
                       m=0;n=1   m=1;n=0

This recursion can be thought of as a Pre-order Traversal of this tree.

If you then consider the conditions of the method for where a solution is found or not. So at the leaf nodes where n = 0.

Each which comes about like this:

First solution

1. m=1;n=3 - Exclude the last coin (2c)
2. m=1;n=2 - Use this coin (1c) and reduce by 1
3. m=1;n=1 - Use this coin (1c) and reduce by 1
4. m=1;n=0 - Use this coin (1c) and reduce by 1
5. n = 0 - a solution (3x1c)

Second Solution

1. m=2;n=1 - Use this coin(2c) and reduce by 2
2. m=1;n=1 - Exclude the last coin (2c)
3. m=1;n=0 - Use this coin (1c) and reduce by 1
4. n = 0 - a solution (1x2c + 1x2c)

At each node a value is returned - 0 (no solution) or 1 (a solution) - to add to the total count of solutions found. Once the recursion ends this final value is returned and is the number of solutions.

---

Some additional notes:

• This piece of code will only consider the first m coins in the array S so to consider all the possible ways the initial call to the method needs to have m == S.length
• Assumes that each coin can be used multiple times

---

Code modification with print statements to see the recursion:

public static void main(String[] args){
    int[] coins = new int[]{1,2};
    System.out.println("Final Count = " + count(coins, coins.length, 3, ""));
}

public static int calls = 0;

public static int count( int S[], int m, int n , String from){
    calls++;
    System.out.print("Call#" + calls + ": " + from + "; m = " + m + "; n = " + n);

    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
    {
        System.out.println(" - Solution Found");
        return 1;
    }

    // If n is less than 0 then no solution exists
    if (n < 0)
    {
        System.out.println(" - No Solution Found n < 0");
        return 0;
    }

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
    {
        System.out.println(" - No Solution Found (other Case)");
        return 0;
    }

    System.out.println();
    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n , from + "E" ) + count( S, m, n-S[m-1], from + "I" );
}