DSA-131 · Unordered unbounded combination counting with exact integers

Coin Change II — Combination Count

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1112 deterministic checks. Learner drafts are not executed.

Understand the problem

Given positive coin denominations and a nonnegative amount, return the number of unordered combinations that sum exactly to the amount. Each denomination may be used any number of times. Equal denomination values describe the same coin type.

coins is a non-null int[] with at most 100 entries, each from 1 through 10000. amount is in 0..10000. Null throws NullPointerException; invalid lengths, values, or amount throw IllegalArgumentException. Validate all denominations even when amount is zero.
Return an exact BigInteger, without a modulus or overflow truncation. Duplicate denomination values are normalized to one type. Preserve coins and its original order; sorting occurs only in a private normalized array.
Return one for amount=0, representing the empty multiset, even when coins is empty. Return zero when no combination exists. Permuting a multiset does not create a different combination. Only the count is returned; the quantity-enumeration baseline is practical only for small inputs.

Examples

Input: coins=[1,2,5], amount=5
Output: 4
The multisets are {5}, {2,2,1}, {2,1,1,1}, and {1,1,1,1,1}.
Input: coins=[1,2], amount=3
Output: 2
{1,1,1} and {1,2}; [1,2] and [2,1] are one multiset.
Input: coins=[2,2], amount=4
Output: 1
Both entries name the same type, so only {2,2} is counted.
Input: coins=[], amount=0
Output: 1
The empty combination is the counting identity.

Before you start

Counting ordered paths versus unordered multisets
Coin-type layers and increasing amount dependencies

Recognize the structure

The output asks for a count of value multisets, not a minimum number of coins and not ordered move sequences. A state must therefore track which denomination types have been introduced. Fixing a type order gives every multiset one construction history. Unlimited reuse then reads a smaller amount in the current type layer. The key optimization is preserving that layer meaning when the type dimension is compressed away.

Try before revealing

Hint 1

Give each multiset a canonical denomination order so it is constructed once.

Hint 2

Split solutions into zero copies of the current type and at least one copy.

Hint 3

Use coin outside and sums increasing inside; initialize ways[0] to BigInteger.ONE.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate a quantity for each distinct type

Normalize and sort denominations, then choose zero, one, two, and so on copies of the current type while the remaining amount stays nonnegative. Recurse to the next type with the resulting remainder. At the end of all types contribute one only when the remainder is zero. Each combination has one quantity vector, so no deduplication of output paths is needed. This baseline is useful for showing why combinations differ from permutations; its search repeats many (type, remainder) subproblems. Verification limits amounts for this search. A separate oracle enumerates nondecreasing value sequences rather than using either quantity vectors or an amount-DP table.

Improve the baseline

Name the full two-dimensional state

C(k,s) is the number of combinations totaling s using only the first k distinct types. C(0,0)=1, C(0,s>0)=0. For any k, C(k,0)=1 because all quantities can be zero. Missing solutions contribute zero, which is a valid count rather than a special unreachable marker.

Separate zero copies from at least one copy

For the kth coin c, combinations with zero copies contribute C(k−1,s). Removing one c from combinations with at least one copy gives C(k,s−c), so C(k,s)=C(k−1,s)+C(k,s−c) for s≥c. These two families are disjoint. For s<c only the zero-copy family fits.

Compress the type layers with the correct loop order

Initialize ways[0]=1 and other entries zero. Process one denomination in the outer loop. Scan sums from c upward, assigning ways[s]+=ways[s−c]. Before the write, ways[s] is from the previous type layer; the smaller ways[s−c] already belongs to the current layer and permits another copy of c. Sums below c remain unchanged.

Trace type ownership

For coins [1,2], amount 3, the table after type 1 is [1,1,1,1]. Type 2 changes sum 2 to two ways and sum 3 to two ways. With amount outside and coins inside, sum 3 instead counts the two different final coins of [1,2] and [2,1], producing three ordered sequences.

Keep exact arithmetic and normalization explicit

BigInteger.ZERO and ONE are immutable, so filling an array with the same ZERO object is safe. add returns a new value; the result must be assigned. Private normalization removes repeated types before counting, rather than trying to divide away duplicates later. Counts can exceed long at supported amounts, so exact arbitrary precision is part of the API, not an optional implementation detail.

Why it is correct

Base layer

With no types, only amount zero is representable, in exactly one way. Initializing only ways[0] to ONE establishes this base, including an empty denomination list.

Type-layer induction

Assume the old layer counts every multiset from earlier types once. Any multiset in the new layer either has no c or loses exactly one c to produce a smaller-sum multiset in the same layer. The inverse construction is unique. Increasing sums ensure this current-layer dependency is final before use, giving soundness, completeness, and no ordering duplicates.

Termination and returned count

There are finitely many normalized types and bounded amounts. At the end of a type scan every sum reflects exactly the types processed so far. After all types, ways[amount] is the requested count. Positive c prevents a self-dependency or nonterminating quantity loop, and BigInteger prevents numerical overflow.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static int[] normalized(int[] coins, int amount) {
        Objects.requireNonNull(coins, "coins");
        if (coins.length > 100 || amount < 0 || amount > 10_000) throw new IllegalArgumentException("bounds");
        for (int coin : coins) if (coin < 1 || coin > 10_000) throw new IllegalArgumentException("positive denomination required");
        return Arrays.stream(coins).distinct().sorted().toArray();
    }
    public static BigInteger change(int[] coins, int amount) {
        int[] values = normalized(coins, amount);
        BigInteger[] ways = new BigInteger[amount + 1];
        Arrays.fill(ways, BigInteger.ZERO);
        ways[0] = BigInteger.ONE;
        for (int coin : values) {
            for (int sum = coin; sum <= amount; sum++) {
                ways[sum] = ways[sum].add(ways[sum - coin]);
            }
        }
        return ways[amount];
    }
    // Baseline: enumerate quantities of each distinct denomination. Small inputs only.
    public static BigInteger baseline(int[] coins, int amount) {
        return quantities(normalized(coins, amount), 0, amount);
    }
    private static BigInteger quantities(int[] values, int index, int remaining) {
        if (index == values.length) return remaining == 0 ? BigInteger.ONE : BigInteger.ZERO;
        BigInteger count = BigInteger.ZERO;
        for (int left = remaining; left >= 0; left -= values[index]) count = count.add(quantities(values, index + 1, left));
        return count;
    }
}

Read the meaningful blocks

Validate and normalize without caller mutation

normalized rejects nonpositive coins and all out-of-range values before producing a sorted distinct array. The amount-zero shortcut cannot accept a malformed denomination. Original array positions have no physical-coin meaning under this contract.

Initialize an exact counting identity

All positive amounts start at ZERO and amount zero starts at ONE. Repeated references to immutable ZERO are safe; mutability assumptions from arrays of lists do not apply to BigInteger.

Read the current smaller sum, then assign add

The outer coin loop owns one type layer. The inner ascending scan permits reuse. ways[sum].add(...) does not mutate ways[sum], so retaining the returned object is essential. The final reference to an immutable BigInteger is safe to return.

Complexity

Let m be raw entries, d distinct types, A the amount, and B a bound on the bit length of any stored count (at least one). Normalization uses expected O(m+d log(d+1)) work; counting uses O(d(A+1)) BigInteger additions. Charging O(B) per addition gives O(m+d log(d+1)+d(A+1)B) time and O(m+(A+1)(B+1)) auxiliary storage measured in bits/words as appropriate. The result itself needs O(B) bits.

A loose count bound is (A+1)^d quantity vectors, hence B=O(1+d log(A+1)). The baseline has a conservative O((A+1)^(d+1)(B+1)) time bound and O(m+(d+1)(B+1)) live workspace including recursive partial counts. These bounds intentionally expose arithmetic size; calling BigInteger addition constant-time would hide part of the cost.

Exact-state walkthroughs

Reveal normal and boundary traces

Type layers prevent permutation duplicates

Input: {"coins":[1,2],"amount":3} · Exact unordered combination count: 2

Step 1 of 10: Normalize private denomination types and seed the empty multiset.

Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.

Combination counts — denomination layers and unlimited reuse

Phase: initial.

Original denominations: [1,2]. Target amount: 3. Equal values name one reusable type.

Private distinct types — one outer-loop layer at a time

Exact combination counts by amount

amount 0: 1no types introduced
amount 1: 0no types introduced
amount 2: 0no types introduced
amount 3: 0no types introduced

ways[0]=1 counts the empty multiset. ZERO is a count, not an unreachable marker. Decimal strings in the state table preserve BigInteger values exactly.

State after this step
Variable	Value
input	`{"coins":[1,2],"amount":3}`
phase	`"initial"`
denominations	`[1,2]`
ways	`["1","0","0","0"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 import java.util.Objects;
 4 
 5 public final class Solution {
 6     private Solution() {}
 7     private static int[] normalized(int[] coins, int amount) {
 8         Objects.requireNonNull(coins, "coins");
 9         if (coins.length > 100 || amount < 0 || amount > 10_000) throw new IllegalArgumentException("bounds");
10         for (int coin : coins) if (coin < 1 || coin > 10_000) throw new IllegalArgumentException("positive denomination required");
11         return Arrays.stream(coins).distinct().sorted().toArray();
12     }
13     public static BigInteger change(int[] coins, int amount) {
14         int[] values = normalized(coins, amount);
15         BigInteger[] ways = new BigInteger[amount + 1];
16         Arrays.fill(ways, BigInteger.ZERO);
17         ways[0] = BigInteger.ONE;
18         for (int coin : values) {
19             for (int sum = coin; sum <= amount; sum++) {
20                 ways[sum] = ways[sum].add(ways[sum - coin]);
21             }
22         }
23         return ways[amount];
24     }
25     // Baseline: enumerate quantities of each distinct denomination. Small inputs only.
26     public static BigInteger baseline(int[] coins, int amount) {
27         return quantities(normalized(coins, amount), 0, amount);
28     }
29     private static BigInteger quantities(int[] values, int index, int remaining) {
30         if (index == values.length) return remaining == 0 ? BigInteger.ONE : BigInteger.ZERO;
31         BigInteger count = BigInteger.ZERO;
32         for (int left = remaining; left >= 0; left -= values[index]) count = count.add(quantities(values, index + 1, left));
33         return count;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Normalize private denomination types and seed the empty multiset.
Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.
input
{"coins":[1,2],"amount":3}
phase
"initial"
denominations
[1,2]
ways
["1","0","0","0"]
Introduce one denomination type.
The table initially describes only earlier types. Amounts smaller than this coin remain unchanged; this complete scan introduces reuse of this type.
input
{"coins":[1,2],"amount":3}
phase
"type-start"
denominations
[1,2]
ways
["1","0","0","0"]
type
0
coin
1
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[1,2],"amount":3}
phase
"add"
denominations
[1,2]
ways
["1","1","0","0"]
type
0
coin
1
sum
1
before
"0"
predecessor
"1"
next
"1"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[1,2],"amount":3}
phase
"add"
denominations
[1,2]
ways
["1","1","1","0"]
type
0
coin
1
sum
2
before
"0"
predecessor
"1"
next
"1"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[1,2],"amount":3}
phase
"add"
denominations
[1,2]
ways
["1","1","1","1"]
type
0
coin
1
sum
3
before
"0"
predecessor
"1"
next
"1"
Introduce one denomination type.
The table initially describes only earlier types. Amounts smaller than this coin remain unchanged; this complete scan introduces reuse of this type.
input
{"coins":[1,2],"amount":3}
phase
"type-start"
denominations
[1,2]
ways
["1","1","1","1"]
type
1
coin
2
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[1,2],"amount":3}
phase
"add"
denominations
[1,2]
ways
["1","1","2","1"]
type
1
coin
2
sum
2
before
"1"
predecessor
"1"
next
"2"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[1,2],"amount":3}
phase
"add"
denominations
[1,2]
ways
["1","1","2","2"]
type
1
coin
2
sum
3
before
"1"
predecessor
"1"
next
"2"
All distinct denomination layers are complete.
The target count includes each multiset once. Input duplicates do not create extra types; zero target always retains the single empty combination.
input
{"coins":[1,2],"amount":3}
phase
"complete"
denominations
[1,2]
ways
["1","1","2","2"]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
"2"

Duplicate denomination is one type

Input: {"coins":[2,2],"amount":4} · Exact unordered combination count: 1

Step 1 of 7: Normalize private denomination types and seed the empty multiset.

Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.

Combination counts — denomination layers and unlimited reuse

Phase: initial.

Original denominations: [2,2]. Target amount: 4. Equal values name one reusable type.

Private distinct types — one outer-loop layer at a time

Exact combination counts by amount

amount 0: 1no types introduced
amount 1: 0no types introduced
amount 2: 0no types introduced
amount 3: 0no types introduced
amount 4: 0no types introduced

ways[0]=1 counts the empty multiset. ZERO is a count, not an unreachable marker. Decimal strings in the state table preserve BigInteger values exactly.

State after this step
Variable	Value
input	`{"coins":[2,2],"amount":4}`
phase	`"initial"`
denominations	`[2]`
ways	`["1","0","0","0","0"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 import java.util.Objects;
 4 
 5 public final class Solution {
 6     private Solution() {}
 7     private static int[] normalized(int[] coins, int amount) {
 8         Objects.requireNonNull(coins, "coins");
 9         if (coins.length > 100 || amount < 0 || amount > 10_000) throw new IllegalArgumentException("bounds");
10         for (int coin : coins) if (coin < 1 || coin > 10_000) throw new IllegalArgumentException("positive denomination required");
11         return Arrays.stream(coins).distinct().sorted().toArray();
12     }
13     public static BigInteger change(int[] coins, int amount) {
14         int[] values = normalized(coins, amount);
15         BigInteger[] ways = new BigInteger[amount + 1];
16         Arrays.fill(ways, BigInteger.ZERO);
17         ways[0] = BigInteger.ONE;
18         for (int coin : values) {
19             for (int sum = coin; sum <= amount; sum++) {
20                 ways[sum] = ways[sum].add(ways[sum - coin]);
21             }
22         }
23         return ways[amount];
24     }
25     // Baseline: enumerate quantities of each distinct denomination. Small inputs only.
26     public static BigInteger baseline(int[] coins, int amount) {
27         return quantities(normalized(coins, amount), 0, amount);
28     }
29     private static BigInteger quantities(int[] values, int index, int remaining) {
30         if (index == values.length) return remaining == 0 ? BigInteger.ONE : BigInteger.ZERO;
31         BigInteger count = BigInteger.ZERO;
32         for (int left = remaining; left >= 0; left -= values[index]) count = count.add(quantities(values, index + 1, left));
33         return count;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Normalize private denomination types and seed the empty multiset.
Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.
input
{"coins":[2,2],"amount":4}
phase
"initial"
denominations
[2]
ways
["1","0","0","0","0"]
Introduce one denomination type.
The table initially describes only earlier types. Amounts smaller than this coin remain unchanged; this complete scan introduces reuse of this type.
input
{"coins":[2,2],"amount":4}
phase
"type-start"
denominations
[2]
ways
["1","0","0","0","0"]
type
0
coin
2
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[2,2],"amount":4}
phase
"add"
denominations
[2]
ways
["1","0","1","0","0"]
type
0
coin
2
sum
2
before
"0"
predecessor
"1"
next
"1"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[2,2],"amount":4}
phase
"add"
denominations
[2]
ways
["1","0","1","0","0"]
type
0
coin
2
sum
3
before
"0"
predecessor
"0"
next
"0"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[2,2],"amount":4}
phase
"add"
denominations
[2]
ways
["1","0","1","0","1"]
type
0
coin
2
sum
4
before
"0"
predecessor
"1"
next
"1"
All distinct denomination layers are complete.
The target count includes each multiset once. Input duplicates do not create extra types; zero target always retains the single empty combination.
input
{"coins":[2,2],"amount":4}
phase
"complete"
denominations
[2]
ways
["1","0","1","0","1"]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
"1"

Empty combination identity

Input: {"coins":[],"amount":0} · Exact unordered combination count: 1

Step 1 of 3: Normalize private denomination types and seed the empty multiset.

Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.

Combination counts — denomination layers and unlimited reuse

Phase: initial.

Original denominations: []. Target amount: 0. Equal values name one reusable type.

Private distinct types — one outer-loop layer at a time

Exact combination counts by amount

amount 0: 1no types introduced

ways[0]=1 counts the empty multiset. ZERO is a count, not an unreachable marker. Decimal strings in the state table preserve BigInteger values exactly.

State after this step
Variable	Value
input	`{"coins":[],"amount":0}`
phase	`"initial"`
denominations	`[]`
ways	`["1"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 import java.util.Objects;
 4 
 5 public final class Solution {
 6     private Solution() {}
 7     private static int[] normalized(int[] coins, int amount) {
 8         Objects.requireNonNull(coins, "coins");
 9         if (coins.length > 100 || amount < 0 || amount > 10_000) throw new IllegalArgumentException("bounds");
10         for (int coin : coins) if (coin < 1 || coin > 10_000) throw new IllegalArgumentException("positive denomination required");
11         return Arrays.stream(coins).distinct().sorted().toArray();
12     }
13     public static BigInteger change(int[] coins, int amount) {
14         int[] values = normalized(coins, amount);
15         BigInteger[] ways = new BigInteger[amount + 1];
16         Arrays.fill(ways, BigInteger.ZERO);
17         ways[0] = BigInteger.ONE;
18         for (int coin : values) {
19             for (int sum = coin; sum <= amount; sum++) {
20                 ways[sum] = ways[sum].add(ways[sum - coin]);
21             }
22         }
23         return ways[amount];
24     }
25     // Baseline: enumerate quantities of each distinct denomination. Small inputs only.
26     public static BigInteger baseline(int[] coins, int amount) {
27         return quantities(normalized(coins, amount), 0, amount);
28     }
29     private static BigInteger quantities(int[] values, int index, int remaining) {
30         if (index == values.length) return remaining == 0 ? BigInteger.ONE : BigInteger.ZERO;
31         BigInteger count = BigInteger.ZERO;
32         for (int left = remaining; left >= 0; left -= values[index]) count = count.add(quantities(values, index + 1, left));
33         return count;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Normalize private denomination types and seed the empty multiset.
Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.
input
{"coins":[],"amount":0}
phase
"initial"
denominations
[]
ways
["1"]
All distinct denomination layers are complete.
The target count includes each multiset once. Input duplicates do not create extra types; zero target always retains the single empty combination.
input
{"coins":[],"amount":0}
phase
"complete"
denominations
[]
ways
["1"]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
"1"

Impossible odd amount

Input: {"coins":[2],"amount":3} · Exact unordered combination count: 0

Step 1 of 6: Normalize private denomination types and seed the empty multiset.

Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.

Combination counts — denomination layers and unlimited reuse

Phase: initial.

Original denominations: [2]. Target amount: 3. Equal values name one reusable type.

Private distinct types — one outer-loop layer at a time

Exact combination counts by amount

amount 0: 1no types introduced
amount 1: 0no types introduced
amount 2: 0no types introduced
amount 3: 0no types introduced

ways[0]=1 counts the empty multiset. ZERO is a count, not an unreachable marker. Decimal strings in the state table preserve BigInteger values exactly.

State after this step
Variable	Value
input	`{"coins":[2],"amount":3}`
phase	`"initial"`
denominations	`[2]`
ways	`["1","0","0","0"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 import java.util.Objects;
 4 
 5 public final class Solution {
 6     private Solution() {}
 7     private static int[] normalized(int[] coins, int amount) {
 8         Objects.requireNonNull(coins, "coins");
 9         if (coins.length > 100 || amount < 0 || amount > 10_000) throw new IllegalArgumentException("bounds");
10         for (int coin : coins) if (coin < 1 || coin > 10_000) throw new IllegalArgumentException("positive denomination required");
11         return Arrays.stream(coins).distinct().sorted().toArray();
12     }
13     public static BigInteger change(int[] coins, int amount) {
14         int[] values = normalized(coins, amount);
15         BigInteger[] ways = new BigInteger[amount + 1];
16         Arrays.fill(ways, BigInteger.ZERO);
17         ways[0] = BigInteger.ONE;
18         for (int coin : values) {
19             for (int sum = coin; sum <= amount; sum++) {
20                 ways[sum] = ways[sum].add(ways[sum - coin]);
21             }
22         }
23         return ways[amount];
24     }
25     // Baseline: enumerate quantities of each distinct denomination. Small inputs only.
26     public static BigInteger baseline(int[] coins, int amount) {
27         return quantities(normalized(coins, amount), 0, amount);
28     }
29     private static BigInteger quantities(int[] values, int index, int remaining) {
30         if (index == values.length) return remaining == 0 ? BigInteger.ONE : BigInteger.ZERO;
31         BigInteger count = BigInteger.ZERO;
32         for (int left = remaining; left >= 0; left -= values[index]) count = count.add(quantities(values, index + 1, left));
33         return count;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Normalize private denomination types and seed the empty multiset.
Only amount zero has one combination before any type is processed. Decimal strings preserve exact BigInteger values without JavaScript rounding.
input
{"coins":[2],"amount":3}
phase
"initial"
denominations
[2]
ways
["1","0","0","0"]
Introduce one denomination type.
The table initially describes only earlier types. Amounts smaller than this coin remain unchanged; this complete scan introduces reuse of this type.
input
{"coins":[2],"amount":3}
phase
"type-start"
denominations
[2]
ways
["1","0","0","0"]
type
0
coin
2
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[2],"amount":3}
phase
"add"
denominations
[2]
ways
["1","0","1","0"]
type
0
coin
2
sum
2
before
"0"
predecessor
"1"
next
"1"
Add zero-copy and at-least-one-copy combination families.
before belongs to the previous type layer; predecessor is already in the current layer because sums increase. These two families are disjoint, and all stored decimal values are exact.
input
{"coins":[2],"amount":3}
phase
"add"
denominations
[2]
ways
["1","0","1","0"]
type
0
coin
2
sum
3
before
"0"
predecessor
"0"
next
"0"
All distinct denomination layers are complete.
The target count includes each multiset once. Input duplicates do not create extra types; zero target always retains the single empty combination.
input
{"coins":[2],"amount":3}
phase
"complete"
denominations
[2]
ways
["1","0","1","0"]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
"0"

Test the contract

Input: coins=[], amount=7
Output: 0
No positive amount is reachable.
Input: coins=[2], amount=3
Output: 0
Parity obstruction.
Input: coins=[5], amount=10
Output: 1
A type can repeat.
Input: coins=[5,2,1,2], amount=5
Output: 4
Input order and duplicate values do not change the answer.
Input: coins=[0], amount=0
Output: IllegalArgumentException
Validate before accepting the empty combination.
Input: coins=[1], amount=10000
Output: 1
Supported upper amount.

Common mistakes and counterexamples

Put amount outside the denomination loop

Counterexample: [1,2], amount 3 yields three ordered paths rather than two multisets.

Fix the type layer in the outer loop.

Scan amounts downward for unlimited reuse

Counterexample: [2], amount 4 would remain zero because the second 2 cannot read the new sum 2 state.

Use ascending sums for unbounded reuse; downward scans model one use per processed item.

Count duplicate values as separate types

Counterexample: [2,2], amount 4 can be attributed to multiple fake type assignments.

Deduplicate denomination values before counting under this value-type contract.

Keep int/long counts or ignore the returned BigInteger

Counterexample: Large counts overflow primitive integers; calling add without assignment leaves counts unchanged.

Return exact BigInteger and assign each immutable addition result.

Follow-ups

Count ordered sequences instead.

Use amount as the outer state and sum over possible final coins. This is the same ordered-path distinction seen in Climbing Stairs. Equal denomination values should still be deduplicated unless the contract intentionally treats them as distinct labeled move types.

Each physical coin can be used once.

Process occurrences separately and scan sums downward so an occurrence cannot feed itself again. Decide whether equal-valued physical coins define distinct subsets or indistinguishable bounded supply; the latter needs a bounded-type recurrence rather than simple occurrence counting.

Produce one combination or enumerate all of them.

Store a feasible predecessor to recover one witness, with a deterministic denomination rule. Enumerating all combinations needs quantity vectors or canonical backtracking and output-sensitive complexity. A count alone contains no witness, and even a small DP table can describe an enormous output set.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 127/20,000 characters

Self-review

I can state the type-layer invariant and why its two families are disjoint.I can explain why swapping loops counts permutations and reversing the inner loop prevents reuse.I can account for duplicate values, BigInteger assignment, zero identity, and bit complexity.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.