title: Algorithm to find all possible binary combinations with a condition
body: <p>Here is one is for you math brains out there.  I have a matrix, actually its half a matrix, cut diagonally. Each element of the matrix can be a <strong>1</strong> or a <strong>0</strong>.   I need to find all the possible combinations of <strong>1</strong>s and <strong>0</strong>s for any matrix of width <strong>N</strong>. </p>
  
  <p>This is easy enough, you can get the number of elements on this matrix given width <strong>N</strong> with <img src="https://chart.googleapis.com/chart?cht=tx&amp;chl=%5Cfrac%7BN*(N%2B1)%7D%7B2%7D" alt="formula"> for this example where <strong>N=7</strong> this would give us <strong>28</strong> or the number of elements. Then you can get the combinations with <img src="https://chart.googleapis.com/chart?cht=tx&amp;chl=2%5E%7B28%7D" alt="formula">.</p>
  
  <p>So the formula would be  <img src="https://chart.googleapis.com/chart?cht=tx&amp;chl=2%5E%7B%5Cfrac%7BN*(N%2B1)%7D%7B2%7D%7D" alt="formula"> to get all the possible combinations.</p>
  
  <p><a href="https://i.stack.imgur.com/0NIqD.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/0NIqD.jpg" alt="empty"></a></p>
  
  <p>Now here is where it gets tricky.  There is one condition that must hold true for each result.  The sum of the each set of elements on the matrix (shown below with each row represented) must be less than 4 for the first set (the one on the first row), less than 3 for all the other sets (these are constants regardless of the N value).  </p>
  
  <p><a href="https://i.stack.imgur.com/7vXGV.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7vXGV.jpg" alt="enter image description here"></a></p>
  
  <p>Here are what the sets for this example (<strong>N=7</strong>) look like.  If you notice each row is represented.  So for the first set if the combination is <strong>0 1 0 1 0 1 0</strong> this would be valid as its sum is &lt; 4 (since its the first row).  For the second set if the combination is <strong>1 0 0 0 0 1 0</strong> it is valid as it needs to be &lt; 3.</p>
  
  <p><a href="https://i.stack.imgur.com/i1Xld.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/i1Xld.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/hjm0Y.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hjm0Y.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/puWTK.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/puWTK.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/DXHbF.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DXHbF.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/ijnsw.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ijnsw.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/kNktC.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/kNktC.jpg" alt="enter image description here"></a>
  <a href="https://i.stack.imgur.com/pHUdZ.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pHUdZ.jpg" alt="enter image description here"></a></p>
  
  <p>I need to do this for huge matrices so brute forcing all possible permutations to find the ones that fall under this condition would be unfeasable.  I need to find some sort of algorithm I can use to generate the valid matrices bottom up rather than top down. Maybe doing separate operations that can be composed later to yield a total set of results.</p>
  
  <p>Any and all ideas are welcome.</p>