Geek Answers Handbook

Recursive method for counting the number of combinations

This is a java code that recursively calculates the number of payments in certain coins (for example, 1, 2, 5, 20, 50, etc.). I tried to figure out how this works, but can't seem to get it. Can anyone be so kind and explain the math and logic of the code and how this recursion works? I would be very grateful.

    // 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] );
}
+4
source share
2 answers

The method works as follows:

  • The first statements are the stopping conditions for the current recursion (without them, for all cases, you end with an infinite loop, which ultimately ends in StackOverFlow)

  • - . :

    • count( S, m - 1, n ) (m-1),
    • count( S, m, n-S[m-1]) ,

:

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

; = count( S, m - 1, n ), = 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

Pre-order .

. , n = 0.

:

  • m = 1; n = 3 - (2c)
  • m = 1; n = 2 - (1c) 1
  • m = 1; n = 1 - (1c) 1
  • m = 1; n = 0 - (1c) 1
  • n = 0 - (3x1c)

  • m = 2; n = 1 - (2c) 2
  • m = 1; n = 1 - (2c)
  • m = 1; n = 0 - (1c) 1
  • n = 0 - (1x2c + 1x2c)

node - 0 ( ) 1 () - . , .

:

  • m S, , , m == S.length
  • ,

, :

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" );
}
+6

, S - m, , n - .

, . count( S, m - 1, n ) - , . count( S, m, n-S[m-1] ) - , .

, m .

, n . m, . , - , 0, n < 0.

- , .

+3

More articles:


All Articles