How to solve coin change task when order does matters?

Question

As I found in here,

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d_1....d_m. It is a general case of Integer Partition, and can be solved with dynamic programming.

The problem is typically asked as: If we want to make change for N cents, and we have infinite supply of each of S = { S_1, S_2,....., S_m } valued coins, how many ways can we make the change? (For simplicity's sake, the order does not matter.)

I tried this and this works fine. So How I can modify this to find all possible coin combinations when the order of different coins actually does matter.

i.e. : before

For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

now :

for N = 4,S = {1,2,3}, there are 7 solutions: {1,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2},{1,3},{3,1}

here {1,1,1,1} even though one can pick the four '1's in different order it has to be considered as one final combination. rather than considering that four coins are different. so actually the order of different coins has to be different to count it as a separate combination.

ex: {1,1,3} won't assume {1_a,1_b,3_a} is a combination and {1_b,1_a,3_a} is another combination with different ordering.

Answer 1

Calculating just the number of solutions is much less effort than enumerating them all.

Lets take the example of S={1,2,3}, and call f(n) the number of solutions for amount n.

Then we have:

f(n) = 0 if n < 0

f(0) = 1

f(n) = f(n-1) + f(n-2) + f(n-3) if n > 0 (where the numbers 1,2,3 are the elements of S)

It is not too difficult to write a program performing these calculations. You could start with the low numbers and work your way up:

f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 7
f(5) = 13
...

For this specific S it turns out each number is just the sum of the preceding three numbers.

How to arrive at this formula? I take again the specific set S={1,2,3} as example, the general case is likewise easy. To count the number of solutions for n look at the first element. It can be 1, 2, or 3. If it is 1, there are f(n-1) ways to arrange the remaining elements. If it is 2 there are f(n-2) ways for the remaining elements and finally if it is 3 there are f(n-3) ways for the remaining elements. The total number must therefore be the sum of the three.