title: How to efficiently generate all combinations (at all depths) whose sum is within a specified range
body: <p>Suppose you have a set of values (<code>1</code>,<code>1</code>,<code>1</code>,<code>12</code>,<code>12</code>,<code>16</code>) how would you generate all possible combinations (without repetition) whose sum is within a predefined range <code>[min,max]</code>. For example, here are all the combinations (of all depths) that have a range between <code>13</code> and <code>17</code>:</p>
  
  <p><code>1</code> <code>12</code></p>
  
  <p><code>1</code> <code>1</code> <code>12</code></p>
  
  <p><code>1</code> <code>1</code> <code>1</code> <code>12</code></p>
  
  <p><code>16</code></p>
  
  <p><code>1</code> <code>16</code></p>
  
  <p>This assumes that each item of the same value is indistinguishable, so you don't have three results of <code>1</code> <code>12</code> in the final output. Brute force is possible, but in situations where the number of items is large, the number of combinations at all depths is astronomical. In the example above, there are (3 + 1) * (2 + 1) * (1 + 1) = 24 combinations at all depths. Thus, the total combinations is the product of the number of items of any given value + 1. Of course we can logically throw out huge number of combinations whose partial sum is greater than the max value (e.g. the set <code>16</code> <code>12</code> is already bigger than the max value of <code>17</code>, so skip any combinations that have a <code>16</code> and <code>12</code> in them).</p>
  
  <p>I originally thought I could convert the input array into two arrays and increment them kind of like an odometer. But I am getting completely stuck on this recursive algorithm that breaks early. Any suggestions?</p>
  
  <pre><code>{
      int uniqueValues = 3;
      int[] maxCounts = new int[uniqueValues];
      int[] values = new int[uniqueValues];
  
      // easy code to bin the data, just hardcoding for example
      maxCounts[0] = 3;
      values[0] = 1;
      maxCounts[1] = 2;
      values[1] = 12;
      maxCounts[2] = 1;
      values[2] = 16;
  
      GenerateCombinationsHelper(new List&lt;int[]&gt;(), 13, 17, 0, 0, maxCounts, new int[3], values);
  }
  
  private void GenerateCombinationsHelper(List&lt;int[]&gt; results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
  {
      if (index &gt;= maxValues.Length)
      {
          return;
      }
  
      while (currentCombo[index] &lt; maxValues[index])
      {
          currentValue += values[index];
  
          if (currentValue&gt; max)
          {                   
              return;
          }
  
          currentCombo[index]++;
  
          if (currentValue&lt; min)
          {                    
              GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
          }
          else
          {
              results.Add((int[])currentCombo.Clone());
          }
      }
  }
  </code></pre>
  
  <p><strong>Edit</strong></p>
  
  <p>The integer values are just for demonstration. It can be any object that has a some sort of numerical value (<code>int</code>, <code>double</code>, <code>float</code>, etc...)</p>
  
  <p>Typically there will only be a handful of unique values (~10 or so) but there can be several thousands total items.</p>