Coin Change II: the idea to remember.

The core insight

Process denominations in a fixed order so adding a coin does not count reordered selections again.

Why it works

Every combination has one nondecreasing denomination order, which the coin dimension enforces.

The mistake to avoid

This counts combinations rather than permutations. Amount zero has one combination: choose no coins.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Process denominations in a fixed order so adding a coin does not count reordered selections again.
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];


    dp[0] = 1;

    for (int coin : coins) {
        for (int i = 1; i <= amount; i++) {
            if (coin <= i) {
                dp[i] += dp[i - coin];
            }
        }
    }

    return dp[amount];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection