title: Project Euler 31: Why does this solution work?
body: <p>I have been studying various solution to Project Euler question #31:</p>
  
  <blockquote>
    <p>In England the currency is made up of pound, £, and pence, p, and
    there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p,
    50p, £1 (100p) and £2 (200p). </p>
    
    <p>It is possible to make £2 in the following way: 1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p </p>
    
    <p>How many different ways can £2 be made using any number of coins?</p>
  </blockquote>
  
  <p>I am confused why this particular brute force solution works (<a href="http://www.mathblog.dk/project-euler-31-combinations-english-currency-denominations/" rel="nofollow">source</a>): </p>
  
  <pre><code>int target  = 200;
  int ways = 0;
  
  for (int a = target; a &gt;= 0; a -= 200) {
      for (int b = a; b &gt;= 0; b -= 100) {
          for (int c = b; c &gt;= 0; c -= 50) {
              for (int d = c; d &gt;= 0; d -= 20) {
                  for (int e = d; e &gt;= 0; e -= 10) {
                      for (int f = e; f &gt;= 0; f -= 5) {
                          for (int g = f; g &gt;= 0; g -= 2) {
                              ways++;
                          }
                      }
                  }
              }
          }
      }
  }
  </code></pre>
  
  <p>Based on this solution I would expect there to be one more nested for-loop at the innermost level that is decrementing by 1, for coins of 1p value. </p>
  
  <p>For example, when do we count the scenario where 200p is made up of only 1p coins? </p>
  
  <p>As it stands currently, the code leads to the correct answer. But if an additional for-loop was added then it would seem the answer should be much bigger. What am I missing?</p>