Lesson 30.3 · Knapsack DP

Coin Change: Combinations vs Permutations

Coins in the outer loop count combinations (order doesn't matter). Amount in the outer loop counts sequences (order matters).

10 min

Think of it like this

Paying 4 with coins 1, 2 and 3. If you only care which coins end up in the till, 1+3 and 3+1 are the same payment. If you care about the order you hand them over, they're different.

1.Loop order decides what you count

Combinations (Coin Change II): for each coin, for each amount upwards: ways[a] += ways[a − coin]. Each coin type is considered in a fixed order, so every multiset is counted once.

Permutations (Combination Sum IV): for each amount, for each coin: ways[a] += ways[a − coin]. Any coin can be last, so different orders count separately.

Fewest coins (Coin Change): best[a] = min(best[a], best[a − coin] + 1); either loop order works because min doesn't care about order.

Main.java

public class Main {
    public static void main(String[] args) {
        int[] coins = {1, 2, 3};
        int target = 4;

        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int coin : coins)                      // coin outer
            for (int a = coin; a <= target; a++) comb[a] += comb[a - coin];

        int[] perm = new int[target + 1];
        perm[0] = 1;
        for (int a = 1; a <= target; a++)           // amount outer
            for (int coin : coins) if (coin <= a) perm[a] += perm[a - coin];

        System.out.println("combinations: " + comb[target]);
        System.out.println("permutations (order matters): " + perm[target]);
    }
}

Output

combinations: 4
permutations (order matters): 7

Remember

Coin outer → combinations.
Amount outer → permutations.
Min/max: order doesn't matter.

Common mistakes

Swapping the loops and getting 7 instead of 4.

Command Palette

Coin Change: Combinations vs Permutations

1.Loop order decides what you count