title: How to find all combinations that sum up to at most a constant?
body: <p>Let <code>P=[P1, P2, ..., Pk]</code> be <code>k</code> positive integers and let <code>T</code> be a positive integer. I would like to generate all combinations that sum up to at most <code>T</code>. That is, <code>sum(x[i] * P[i] for i in 1:k) &lt;= T</code> where <code>x[i] = 1</code> iff <code>i</code> is chosen in the combination.</p>
  
  <p>Example.</p>
  
  <p>Let <code>P=[1, 2, 3]</code> and <code>T=4</code>. The combinations should be: </p>
  
  <pre><code>1
  2
  3
  1, 2
  1, 3
  2, 3
  </code></pre>
  
  <p>So only the combination <code>1, 2, 3</code> cannot be there because <code>1 + 1 + 3 = 5 &gt; 4</code>.</p>
  
  <p>I thought of generating all combinations first and then start verifying the constraint <code>sum(x[i] * P[i] for i in 1:k) &lt;= T</code>. But this approach could be more time consuming than other clever approaches. How can we generate such combinations?</p>
  
  <p>NB. If you know any function in Python or Matlab that can be used to generate such combinations, you can provide it.</p>
  
  <p>Thank you.</p>