title: How to solve coin change task when order does matters?
body: <p>As I found in <a href="http://www.algorithmist.com/index.php/Coin_Change" rel="nofollow">here</a>,</p>
  
  <p>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.</p>
  
  <p>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? <strong>(For simplicity's sake, the order does not matter.)</strong></p>
  
  <p>I tried this and this works fine. So How I can modify this to find all possible coin combinations when the <strong>order of different coins actually does matter</strong>.</p>
  
  <p>i.e. : before</p>
  
  <p>For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.</p>
  
  <p>now : </p>
  
  <p>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}</p>
  
  <p>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.</p>
  
  <p>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.   </p>