title: Coin Change: number of solutions when order matters vs. when order doesn't matter
body: <p>I solved the coin change problem with dynamic programming with the following functions count_distinct and count_perm, which both give the number of solutions for the given amount of money (parameter x) and the coins in use (parameter c). The vector d is used for memoization: it records the number of solutions for each nonnegative amount of money, i.e. for the values {0,1,...,x}.</p>
  
  <p>As an example, when the amount of money is 5 and the coins in use are {2, 3, 4}, count_distinct gives the result 1 (it considers the solutions {2, 3} and {3, 2} as equal), and count_perm gives the result 2 (it considers them as different solutions).</p>
  
  <p>I don't understand the reason for why this happens. In the two functions, the loop variables are in opposite order, but I don't see why that should matter. Also, the indexation in count_distinct takes care that negative amounts of money aren't evaluated, and the corresponding check is done with the continue-statement in count_perm.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  using namespace std;
  
  long count_distinct(int x, vector &lt;long&gt; c) {
  
      vector &lt;long&gt; d(x+1);
      d[0] = 1;
      int k = c.size();
  
      for (int i = 0; i &lt; k; i++) {
          for (int j = c[i]; j &lt;= x; j++) {
              d[j] += d[j - c[i]];
          }
      }
      return d[x];   
  }
  
  long count_perm(int x, vector &lt;long&gt; c) {
  
      vector &lt;long&gt; d(x + 1);
      d[0] = 1;
      int k = c.size();
  
      for (int i = 1; i &lt;= x; i++) {
          for (int j = 0; j &lt; k; j++) {
              if (i - c[j] &lt; 0) continue;
              d[i] += d[i - c[j]];
          }
      }
      return d[x];
  }
  
  int main() {
      int x = 5;
      vector &lt;long&gt; c;
      c.push_back(2);
      c.push_back(3);
      c.push_back(4);
  
      long distinct = count_distinct(x, c);
      long perms = count_perm(x, c);
      cout &lt;&lt; distinct &lt;&lt; endl;
      cout &lt;&lt; perms &lt;&lt; endl;
      return 0;
  }
  </code></pre>