Counting Coin Combinations — Solution & Editorial

Back to the Problem

Loop coins on the OUTSIDE and amounts inside — that counts each multiset once. Swapping the loops counts ordered sequences instead.

Complexity: O(N·T)

Watch out: Loop order is the whole problem: amounts-outer counts permutations, coins-outer counts combinations.