Interview Question for Software Engineering Intern at Google:

To make it efficient, you need to use dynamic programming:

int ways[MAX];
int numWaysToMakeChange(int amount, int denominations[], int nden) {
    memset( ways , 0 , sizeof ways );
    sort( denominations, denominations + nden );
    ways[0] = 1;
    for (int i = nden-1 ; i >= 0 ; i--)
        for (int am = denominations[i] ; am <= amount ; am++)
            ways[am] += ways[am-denominations[i]];
    return ways[amount];
}