205. Coin Change - Count Number of Ways

Given n coin denominations (unlimited supply of each) and a target amount, count the number of distinct ways (as multisets of coins - order doesn't create a new way) to make exactly that amount.

Input: The first line contains an integer n, the number of coin denominations. The second line contains n space-separated integers, the coin values. The third line contains an integer amount, the target. Output: Print a single integer - the number of distinct ways (as multisets, order-independent) to make exactly that amount.

1 <= n <= 100, 0 <= amount <= 10^5

Swapping the loop order (amounts outer, coins inner) would instead count ORDERED sequences of coins (permutations, not combinations) - a genuinely different question, useful to know as a related variant.

Count the number of distinct ways (as multisets) to make a target amount using given coin denominations. Brute force: Try every possible combination of coin counts summing to the target directly, without a systematic processing order - this risks either missing combinations or double-counting the same multiset represented in different orders. Optimised: Processing coins ONE AT A TIME (completing all updates for one coin type before moving to the next) ensures each distinct MULTISET of coins is counted exactly once - if instead you looped over coins on the INSIDE for every amount, the same combination could be counted multiple times in different orders (like counting 1+2 and 2+1 as separate ways, which they shouldn't be for this unordered-combination version).

Maintain a single array dp of size amount+1 with dp[0] = 1 (one way to make zero, using no coins), and for each coin denomination in turn, update dp by scanning amounts from the coin's value up to the target, adding dp[j - coin] into dp[j]. This is correct because processing one whole denomination at a time before moving to the next guarantees that each combination is only ever counted once, in a canonical order, and reusing a single array in place of a 2D table removes the dependency on the denomination-index dimension. Time: O(n * amount) Space: O(amount)

Use the same recursive structure as the brute force, but cache the result for each (current denomination index, remaining amount) pair the first time it is computed, and reuse the cached answer instead of recomputing it whenever the same pair is reached again. This is correct because the number of ways to make a remaining amount from a suffix of the denominations only ever depends on those two values, so memoizing collapses what would otherwise be repeated exponential recursion into one computation per distinct state. Time: O(n * amount) Space: O(n * amount)

Recursively decide, for each coin denomination in turn, how many copies of it to use (0, 1, 2, ... up to the amount) before moving on to the next denomination, and count the recursion branches that land on exactly the target amount using no coin more than once per denomination choice ordering (to avoid counting the same multiset twice, always move to later denominations once you stop using an earlier one). This correctly counts every distinct combination because it mirrors exactly how multisets of coins are built up denomination by denomination, but it re-explores overlapping (denomination-index, remaining-amount) states repeatedly, causing exponential blowup. Time: O(2^amount) Space: O(n)

1. dp[a] = number of ways to make amount a; dp[0]=1 (one way: use no coins at all). 2. Process ONE coin denomination AT A TIME, fully updating dp[a] += dp[a-coin] for every a >= coin, in increasing order of a, before moving to the next coin. 3. Processing coins one at a time (rather than mixing all coins together per amount) is exactly what prevents counting the same combination multiple times in different orders.

Time: O(n * amount) - for each of the n coins, updating all reachable amounts. Space: O(amount), for the dp array.

Test amount = 0 (exactly one way: use no coins), an amount unreachable by any combination of the given coins (answer 0), and n at the upper bound of 100 with amount at the upper bound of 10^5 for performance.

Be ready to explain PRECISELY why the loop order (coins outer, amounts inner) prevents double-counting - this is one of the most commonly confused DP loop-ordering subtleties, and getting it backwards silently produces a wrong (larger) count.