java - How to solve coin change task when order does matters? -

as found in here,

coin change problem of finding number of ways of making changes particular amount of cents, n, using given set of denominations d_1....d_m. general case of integer partition, , can solved dynamic programming.

the problem typically asked as: if want make change n cents, , have infinite supply of each of s = { s_1, s_2,....., s_m } valued coins, how many ways can make change? (for simplicity's sake, order not matter.)

i tried , works fine. how can modify find possible coin combinations when order of different coins matter.

i.e. : before

for example, n = 4,s = {1,2,3}, there 4 solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

now :

for n = 4,s = {1,2,3}, there 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} though 1 can pick 4 '1's in different order has considered 1 final combination. rather considering 4 coins different. order of different coins has different count separate combination.

ex: {1,1,3} won't assume {1_a,1_b,3_a} combination , {1_b,1_a,3_a} combination different ordering.

calculating number of solutions less effort enumerating them all.

lets take example of s={1,2,3}, , call f(n) number of solutions amount n.

then 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 numbers 1,2,3 elements of s)

it not difficult write program performing these calculations. start low numbers , work way up:

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

for specific s turns out each number sum of preceding 3 numbers.

how arrive @ formula? take again specific set s={1,2,3} example, general case likewise easy. count number of solutions n @ first element. can 1, 2, or 3. if 1, there f(n-1) ways arrange remaining elements. if 2 there f(n-2) ways remaining elements , if 3 there f(n-3) ways remaining elements. total number must therefore sum of three.