janco maneh

#include<stdio.h>


// 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] );
}

// Driver program to test above function
int main()
{
    int i, j;
    int arr[] = {1, 3, 5};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 5));
    getchar();
    return 0;
}



It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for S = {1, 2, 3} and n = 5.
The function C({1}, 3) is called two times. If we draw the complete tree, then we can see that there are many subproblems being called more than once.

C() --> count()
 C({1,2,3}, 5) 
 / 
 / 
 C({1,2,3}, 2) C({1,2}, 5)
 / / 
 / / 
C({1,2,3}, -1) C({1,2}, 2) C({1,2}, 3) C({1}, 5)
 / / / 
 / / / 
 C({1,2},0) C({1},2) C({1,2},1) C({1},3) C({1}, 4) C({}, 5)
 / / / / 
 / / / / 
 . . . . . . C({1}, 3) C({}, 4)
 / 
 /