title: Project Euler #31
body: <p>Problem Description:</p>
  
  <blockquote>
    <p>In England the currency is made up of pound, £, and pence, p, and
    there are eight coins in general circulation:</p>
  
  <pre><code>1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
  </code></pre>
    
    <p>It is possible to make £2 in the following way:</p>
  
  <pre><code>1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
  </code></pre>
    
    <p>How many different ways can £2 be made using any number of coins?</p>
  </blockquote>
  
  <p>I've tried to come up with my own algorithm for this and failed. So, I came upon <a href="https://stackoverflow.com/questions/5897184/algorithm-to-determine-coin-combinations">this one</a> (the accepted answer). I've tried to replicate it in C++ here. When I enter 1, 2, and 5 into combos() in the main() function, it comes up with the right answer, but 10 returns 11, when it should be 12. What's wrong with my algorithm?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;cstdlib&gt;
  using namespace std;
  
  int coin[] = {1, 2, 5, 10, 20, 50, 100, 200};
  
  /*Amounts entered must be in pence.*/
  int combinations(int amount, int size) {
      int comboCount = 0;
  
      if(amount &gt; 0) {
          if(size &gt;= 0 &amp;&amp; amount &gt;= coin[size])
              comboCount += combinations(amount - coin[size], size);
          if(size &gt; 0) //don't do if size is 0
              comboCount += combinations(amount, size-1);
      } else if(amount == 0)
          comboCount++;
  
      return comboCount;
  }
  
  int combos(int amount) {
      int i = 0;
      //get largest coin that fits
      for(i = 7; coin[i] &gt; amount &amp;&amp; i &gt;= 0; i--); 
      return combinations(amount, i);
  }
  
  int main() {
      cout &lt;&lt; "Answer: " &lt;&lt; combos(10) &lt;&lt; endl;
      return 0;
  }
  </code></pre>