⚙️AlgorithmIntermediate

Coin Change and Variants

Key Points

•
Coin Change uses dynamic programming to find either the minimum number of coins to reach a target or the number of ways to reach it.
•
For minimum coins with unlimited supply, use dp[a] = min over coins of dp[a - coin] + 1 with dp[0] = 0.
•
To count combinations where order does not matter, loop coins on the outside and amounts on the inside increasing: dp[a] += dp[a - coin].
•
To count permutations where order matters, loop amounts on the outside and coins on the inside: dp[a] += dp[a - coin].
•
For bounded coins (limited counts), iterate coins outside and amounts descending to enforce usage limits.
•
Use a large INF sentinel and guard conditions to avoid overflow when computing minimum coins.
•
Space can be reduced to O(A) with 1D DP for both minimum and counting variants.
•
Common bugs come from the wrong loop order, forgetting dp[0] = 1 in counting, and integer overflow without modulo.

Prerequisites

→Dynamic Programming Basics — Understanding states, transitions, and base cases is essential to formulate coin change recurrences.
→Nested Loops and Iteration Order — Correct counting depends on whether coins or amounts loop outermost.
→Arrays and Indexing — DP is stored in arrays; careful indexing prevents out-of-bounds errors.
→Big-O Complexity — To assess feasibility for given constraints and choose optimizations.
→Modulo Arithmetic — Counting answers often require modulo to avoid overflow.
→Knapsack Variants (0/1 and Unbounded) — Coin change is a special case; bounded versions mirror knapsack logic.
→Combinatorics: Permutations vs Combinations — Determines whether order should be counted and how to structure loops.
→Integer Overflow and Data Types — Counting can exceed 32-bit; choose long long or apply modulus.

Detailed Explanation

Tap terms for definitions

01Overview

Coin Change problems ask: given coin denominations and a target amount A, how can we assemble A using those coins? There are two core tasks. First, the optimization version: find the minimum number of coins needed to total A. Second, the counting version: count how many ways to make A. Each splits further depending on whether coin order matters (permutations) or not (combinations), and whether coin supply is unlimited (unbounded) or limited (bounded). Dynamic programming (DP) is a natural fit because the decision of how to build A depends on how we can build smaller amounts. We define a DP array where dp[a] represents an answer for amount a, and transition from smaller amounts using each coin value. With careful base cases and loop ordering, we can solve all variants in O(nA) time for n coin types and target A, using only O(A) memory. The key insights include: (1) choosing the right DP meaning and base value (dp[0] = 0 for minimum, dp[0] = 1 for counting), (2) using a large sentinel (INF) for impossible states in the minimum version, and (3) using different loop orders to avoid overcounting. For bounded supplies, we either add an inner loop that caps usage per coin or transform counts via binary splitting into 0/1 items. These patterns appear frequently in competitive programming at the 1200–1600 rating range.

02Intuition & Analogies

Imagine you are a cashier trying to make exact change. If your goal is to use the fewest coins, you’ll try larger coins first, but sometimes a greedy pick fails (like trying to make 6 with coins 1, 3, 4: greedy chooses 4 then 1 then 1, total 3 coins, but optimal is 3 + 3, which is 2 coins). So you need a systematic plan: consider every way you could finish the job by asking, “If I use coin c last, could I have made the remaining amount a − c?” This backward way of thinking is quintessential dynamic programming: the solution to a big problem builds on solutions to smaller subproblems. For counting, think of stacking coins into a pile that sums to A. If order matters (permutations), then 1+2 and 2+1 are different stacks; for each exact height a, you can try placing any coin on top of a smaller stack of height a − coin. If order does not matter (combinations), treat coins like indistinguishable buckets; you enumerate how many of each coin you take without caring about order. The loop structure subtly enforces this: processing amounts in increasing order with coins outside prevents counting the same set in multiple orders. For bounded supplies, picture having a limited number of each coin in rolls. As you build your total, you must not exceed the available rolls. The descending amount loop acts like a one-time stamp: once you add a certain number of a coin, you can’t use it again within that coin’s turn, mirroring limited inventory. These metaphors—finishing with a last coin, stacking piles, and spending from limited rolls—map directly to the DP transitions and loop orders.

03Formal Definition

Let coins be C = {

c_{1}

c_{2}

\dots

c_{n}

} and target amount A. For the minimum-coins, unbounded case define

d p_{min}

[a] as the minimum number of coins to reach a; base

d p_{min}

[0] = 0 and

d p_{min}

[a] = +

\infty

for

a > 0

initially. The transition is

d p_{min}

[a] =

min_{c \in C, a \geq c}

d p_{min}

[a - c] + 1 \}. If

d p_{min}

[A] = +

\infty

, A is unreachable. For counting, define

d p_{c n t}

[a] as the number of ways to reach a with

d p_{c n t}

[0] = 1. There are two variants. Permutations (order matters): process amounts a from 1 to A and accumulate over coins:

d p_{p er m}

[a] =

\sum_{c \in C, a \geq c}

d p_{p er m}

[a - c]. Combinations (order does not matter): process coins outer and amounts a increasing: for each coin c, for a from c to A, set

d p_{co mb}

[a] +=

d p_{co mb}

[a - c]. In bounded cases where coin

c_{i}

can be used at most

k_{i}

times, a standard DP uses for each coin i: for a from A down to 0, for t from 1 to

k_{i}

with a - t

c_{i}

\geq

0, dp[a] += dp[a - t

c_{i}

]; descending amounts prevent reusing the same coin instance multiple times. All transitions run in O(nA) time for unbounded variants and O(A

\sum

k_{i}

) for the naive bounded variant, or O(A

\sum

lo g

k_{i}

) with binary splitting. Space can be compressed to O(A) because each state depends on smaller amounts within the same array under controlled traversal orders.

04When to Use

Use Coin Change DP whenever a target value must be composed from reusable parts, especially when greedy choices are not guaranteed to be optimal. Typical applications include classic minimum-coin change, counting the number of sums achievable from a multiset of integers, and knapsack-like subproblems where item weights equal values. In competitive programming, you’ll use the minimum version to compute shortest compositions with uniform step costs, e.g., the fewest moves to reach a number using allowed increments. You’ll use the counting version to compute the number of sequences or multisets that add to a target, often with modulo arithmetic to avoid overflow. Choose the combinations variant (coins outer, amounts inner increasing) when order should not matter—for example, how many sets of banknotes form a sum. Choose the permutations variant (amounts outer) when order matters—for example, number of different ordered steps to climb stairs with given step sizes. For bounded inventories, switch to descending loops or 0/1 transformations (binary splitting) when each coin has a limited count. If constraints are around n ≤ 100 and A ≤ 1e5, the O(nA) 1D DP is appropriate and standard for 1200–1600 CF problems. If \sum k_i is large but n is modest, consider binary splitting to keep things within time limits.

⚠️Common Mistakes

Common pitfalls include: (1) Wrong base cases: for counting, dp[0] must be 1 (one empty way), not 0; for minimum coins, dp[0] = 0 and others should start at a large INF. (2) Overflow: counting grows quickly; use 64-bit integers or apply a modulus like 1,000,000,007. Be consistent with modulo in every addition. (3) Overcounting due to loop order: if you intend combinations (order does not matter) but loop amounts outer and coins inner, you count each multiset many times. Always remember: combinations → coins outer, amounts inner increasing; permutations → amounts outer, coins inner. (4) Violating bounded limits: when coins are limited, you must either traverse amounts in descending order for each coin or track usage counts; otherwise, a single coin can be used more than allowed. (5) Using INF incorrectly: adding 1 to INF can overflow; always check reachability (dp[a - c] < INF) before adding. (6) Ignoring unreachable states: min-coin DP may leave dp[A] at INF; handle this by outputting -1 or a clear message. (7) Off-by-one or negative indices: guard transitions with a ≥ coin. (8) Assuming greedy works: coin systems like {1, 3, 4} break greedy; rely on DP. (9) Re-initialization across test cases: reset dp arrays and base cases properly. (10) Misinterpreting problem variant: confirm whether order matters, whether coins are unlimited, and whether the answer requires modulo.

Key Formulas

Minimum Coins (Unbounded)

d p_{min} [0] = 0, d p_{min} [a] = c \in C, a \geq c min {d p_{min} [a - c] + 1}

Explanation: The fewest coins to make amount a equals one coin plus the best way to make a − c over all coin choices. Start with d $p_{m} in$ [0] = 0.

Counting Permutations (Order Matters)

d p_{p er m} [0] = 1, d p_{p er m} [a] = c \in C, a \geq c \sum d p_{p er m} [a - c]

Explanation: Number of ordered sequences to reach a equals the sum of ways to reach a − c for each coin placed last. The empty sequence counts as one way for a = 0.

Counting Combinations (Order Does Not Matter)

d p_{co mb} [0] = 1, \forall c \in C, \forall a \in [c, A] : d p_{co mb} [a] + = d p_{co mb} [a - c]

Explanation: Processing coins one by one and updating amounts in ascending order ensures each multiset is counted exactly once regardless of order.

Unreachability Test

If d p_{min} [A] = + \infty, then A is unreachable

Explanation: A large sentinel represents impossible amounts. If the final state remains INF, there is no way to form A with the given coins.

Unbounded Complexity

Time = O (n A), Space = O (A)

Explanation: For n coin types and target A, each state a considers all coins, and only a 1D array of size A+1 is needed.

Bounded Combinations Transition

\forall i : \forall a ↓ 0 : \forall t \in [1, k_{i}] : a - t c_{i} \geq 0 ⟹ d p [a] + = d p [a - t c_{i}]

Explanation: For coin i with limit $k_{i}$ , traverse amounts descending and add ways that use t copies. Descending order avoids reusing the same coin copies.

Binary Splitting Count

i = 1 \sum n lo g_{2} (k_{i} + 1) = O (i = 1 \sum n lo g k_{i})

Explanation: Decomposing $k_{i}$ copies into powers of two creates O(log $k_{i}$ ) $\frac{0}{1}$ items per coin, improving bounded DP from linear in $k_{i}$ to logarithmic.

GCD Feasibility (Necessary Condition)

g cd (C) ∤ A \Rightarrow no solution (unbounded)

Explanation: If the greatest common divisor of all coin values does not divide A, then no nonnegative integer combination of coins can sum to A.

Bounded Minimum Coins

d p [a] = min (d p [a], d p [a - t c] + t) (bounded min coins)

Explanation: When limiting uses to t copies of coin c, we can update the minimum coins for amount a by considering spending t copies at once.

Generating Function (Unbounded Combinations)

a = 0 \sum A d p [a] \cdot x^{a} = i = 1 \prod n (1 + x^{c_{i}} + x^{2 c_{i}} + \dots)

Explanation: The coefficient of $x^{A}$ in this product equals the number of combinations to make A. DP computes the same values iteratively.

Complexity Analysis

For unbounded variants (minimum coins, combinations, permutations), the standard DP uses a 1D array of size A+1. Each state a either iterates over all n coins (amounts outer) or each coin iterates over A amounts (coins outer). In both cases, the total time is O(nA). Space is O(A), since only the current array of amounts is stored. For minimum coins, each update is O(1), guarded to avoid adding to INF; thus the overall complexity remains O(nA). For counting, integer additions dominate; if a modulus is applied, modulo operations are O(1). For bounded variants with per-coin limits

k_{i}

, the straightforward triple loop (coins outer, amounts descending, t from 1 to

k_{i}

) executes at most

\sum_{i}

k_{i}

iterations per amount bucket a up to A, giving O(A

\sum_{i}

k_{i}

) time and O(A) space. When

\sum

k_{i}

is large, binary splitting (decomposing

k_{i}

into powers of two) converts each bounded coin into O(log

k_{i}

)

\frac{0}{1}

items. Applying

\frac{0}{1}

DP per pseudo-item yields O(A

\sum_{i}

log

k_{i}

) time, still with O(A) space by descending amount traversal. In practice, for CF constraints around

n \leq 100

and

A \leq 1 e 5

, O(nA) with careful constants passes comfortably. Memory remains linear in A, which is usually safe under 512 MB limits. Edge cases (like unreachable targets) do not alter asymptotic costs but require constant-time checks at the end. Beware that using 64-bit integers is recommended for counting without modulus to avoid overflow, though many problems request answers modulo a prime, keeping arithmetic bounded.

Code Examples

Minimum Coins (Unbounded Supply)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int main() {
5     ios::sync_with_stdio(false);
6     cin.tie(nullptr);
7 
8     int n, A;
9     cin >> n >> A;
10     vector<int> coins(n);
11     for (int i = 0; i < n; ++i) cin >> coins[i];
12 
13     const int INF = 1e9; // large sentinel for unreachable states
14     vector<int> dp(A + 1, INF);
15     dp[0] = 0; // zero coins needed to make amount 0
16 
17     for (int a = 1; a <= A; ++a) {
18         for (int c : coins) {
19             if (a >= c && dp[a - c] < INF) {
20                 dp[a] = min(dp[a], dp[a - c] + 1);
21             }
22         }
23     }
24 
25     if (dp[A] >= INF) {
26         cout << -1 << '\n'; // unreachable
27     } else {
28         cout << dp[A] << '\n';
29     }
30     return 0;
31 }
32

Computes the minimum number of coins to make exact amount A with unlimited copies of each coin. The DP state dp[a] stores the fewest coins for amount a, built from dp[a - c] + 1 for every coin c. A large INF prevents using impossible subproblems.

Time: O(nA)Space: O(A)

Count Ways: Combinations (Order Does Not Matter, Unbounded)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int main() {
5     ios::sync_with_stdio(false);
6     cin.tie(nullptr);
7 
8     int n, A; long long MOD;
9     cin >> n >> A >> MOD; // provide modulus (e.g., 1000000007)
10     vector<int> coins(n);
11     for (int i = 0; i < n; ++i) cin >> coins[i];
12 
13     vector<long long> dp(A + 1, 0);
14     dp[0] = 1; // one empty way to form 0
15 
16     // Coins outer, amounts inner increasing => combinations (orderless)
17     for (int c : coins) {
18         for (int a = c; a <= A; ++a) {
19             dp[a] += dp[a - c];
20             if (MOD) dp[a] %= MOD; // apply modulo if nonzero
21         }
22     }
23 
24     cout << (MOD ? dp[A] % MOD : dp[A]) << '\n';
25     return 0;
26 }
27

Counts the number of multisets of coins that sum to A. By iterating coins on the outside and amounts in ascending order, each combination is counted exactly once. Using a modulus avoids overflow.

Time: O(nA)Space: O(A)

Count Ways: Permutations (Order Matters, Unbounded)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int main() {
5     ios::sync_with_stdio(false);
6     cin.tie(nullptr);
7 
8     int n, A; const long long MOD = 1000000007LL;
9     cin >> n >> A;
10     vector<int> coins(n);
11     for (int i = 0; i < n; ++i) cin >> coins[i];
12 
13     vector<long long> dp(A + 1, 0);
14     dp[0] = 1; // one empty sequence to form 0
15 
16     // Amounts outer, coins inner => permutations (order matters)
17     for (int a = 1; a <= A; ++a) {
18         for (int c : coins) {
19             if (a >= c) {
20                 dp[a] += dp[a - c];
21                 dp[a] %= MOD;
22             }
23         }
24     }
25 
26     cout << dp[A] << '\n';
27     return 0;
28 }
29

Counts ordered sequences of coins that sum to A. Iterating amounts outside ensures dp[a] uses all dp[a − c] from the current array, effectively distinguishing different orderings.

Time: O(nA)Space: O(A)

Bounded Coins: Count Combinations with Limited Copies

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int main() {
5     ios::sync_with_stdio(false);
6     cin.tie(nullptr);
7 
8     int n, A; const int MOD = 1000000007;
9     cin >> n >> A;
10     vector<int> c(n), k(n);
11     for (int i = 0; i < n; ++i) cin >> c[i] >> k[i]; // coin value and its count limit
12 
13     vector<int> dp(A + 1, 0);
14     dp[0] = 1; // one empty way to form 0
15 
16     // For each coin, traverse amounts descending to enforce limited usage (0/1-like per copy within this coin)
17     for (int i = 0; i < n; ++i) {
18         int coin = c[i];
19         int lim = k[i];
20         // For each amount, try using t copies (1..lim) without exceeding amount
21         // Descending amounts avoid reusing the same coin copies multiple times
22         for (int a = A; a >= 0; --a) {
23             long long add = 0;
24             for (int t = 1; t <= lim; ++t) {
25                 int prev = a - t * coin;
26                 if (prev < 0) break;
27                 add += dp[prev];
28                 if (add >= (long long)MOD) add %= MOD;
29             }
30             dp[a] = (dp[a] + (int)(add % MOD)) % MOD;
31         }
32     }
33 
34     cout << dp[A] << '\n';
35     return 0;
36 }
37

Counts combinations to form A when each coin i can be used at most k[i] times. For each coin, we iterate amounts in descending order and try t copies up to the limit. Descending traversal ensures each coin's limited copies are not reused within the same iteration, yielding orderless counting.

Time: O(A * \sum k_i)Space: O(A)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	int main() {
5	ios::sync_with_stdio(false);
6	cin.tie(nullptr);
7
8	int n, A;
9	cin >> n >> A;
10	vector<int> coins(n);
11	for (int i = 0; i < n; ++i) cin >> coins[i];
12
13	const int INF = 1e9; // large sentinel for unreachable states
14	vector<int> dp(A + 1, INF);
15	dp[0] = 0; // zero coins needed to make amount 0
16
17	for (int a = 1; a <= A; ++a) {
18	for (int c : coins) {
19	if (a >= c && dp[a - c] < INF) {
20	dp[a] = min(dp[a], dp[a - c] + 1);
21	}
22	}
23	}
24
25	if (dp[A] >= INF) {
26	cout << -1 << '\n'; // unreachable
27	} else {
28	cout << dp[A] << '\n';
29	}
30	return 0;
31	}
32