title: How to efficiently get all combinations where the sum is 10 or below in Python
body: <p>Imagine you're trying to allocate some fixed resources (e.g. <code>n=10</code>) over some number of territories (e.g. <code>t=5</code>). I am trying to find out efficiently how to get all the combinations where the sum is <code>n</code> or below. </p>
  
  <p>E.g. <code>10,0,0,0,0</code> is good, as well as <code>0,0,5,5,0</code> etc., while <code>3,3,3,3,3,3</code> is obviously wrong.</p>
  
  <p>I got this far:</p>
  
  <pre><code>import itertools
  t = 5
  n = 10
  r = [range(n+1)] * t
  for x in itertools.product(*r): 
     if sum(x) &lt;= n:          
         print x
  </code></pre>
  
  <p>This brute force approach is incredibly slow though; there must be a better way?</p>
  
  <p>Timings (1000 iterations):</p>
  
  <pre><code>Default (itertools.product)           --- time: 40.90 s
  falsetru recursion                    --- time:  3.63 s
  Aaron Williams Algorithm (impl, Tony) --- time:  0.37 s
  </code></pre>