0

FROM HERE

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Recursive solution. (Can someone please help me understand how to calculate time complexity of this solution)

How to solve T(M,N) = T(M,N-1) + T(M-1,N)

int count( int S[], int m, int n )
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;

    if (m <=0 && n >= 1)
        return 0;
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

int main()
{
    int i, j;
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 4));
    getchar(); return 0;
}
Andy897
  • 6,915
  • 11
  • 51
  • 86
  • What do you think it is? Why do you think that? I ask because trying to explain your thoughts for others can often help you to new insights and better understanding of the problems. – Some programmer dude Feb 06 '15 at 08:21
  • The recursive tree is n * m deep at most. But it has lots of branches with duplicates. I dont know how to proceed from there – Andy897 Feb 06 '15 at 08:41
  • T(N,M) = T(N,M-1) + T(N-1,M) – Andy897 Feb 06 '15 at 08:42
  • If I had to guess it looks like `O(n!)` but I'm rusty as hell in my theory, this is useful read if you're learning: http://stackoverflow.com/a/487278/360211 – weston Feb 06 '15 at 09:06

0 Answers0