Count ways to make change

Challenge

Implement:

long long count_change(const int *coins, int nc, int amount);

Return the number of distinct combinations (order-independent) of coins that sum to amount.

Input format

coins, nc, non-negative amount.

Output format

Number of combinations.

Constraints

Iterate coins in the outer loop to avoid counting orderings.

Starter code

#include <stddef.h>
/* Number of distinct combinations of coins (order-independent, unlimited each) summing to amount. amount>=0. */
long long count_change(const int *coins,int nc,int amount){ (void)coins;(void)nc;(void)amount; return 0; }

Common mistakes

Putting the amount loop outside the coin loop counts permutations, not combinations.

Edge cases to handle

amount 0 has exactly 1 way (the empty set).

Background lessons

• Coin change