Consider coins and amount . The combinations are: . That's ways. But if you count and separately, you get ways. The naive approach: for each amount, try all coins.
This counts permutations because you might add coin 1, then coin 2, OR coin 2, then coin 1. The fix: for each coin, update all amounts. This keeps you process coins in a fixed order. Once you've "moved past" a coin, you never go back to it. That's what makes combinations work.