title: Generate all subset sums within a range faster than O((k+N) * 2^(N/2))?
body: <p>Is there a way to generate <i>all</i> of the subset sums s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub> that fall in a range [A,B] faster than O((k+N)*2<sup>N/2</sup>), where k is the number of sums there are in [A,B]? Note that k is only known after we have enumerated all subset sums within [A,B].</p>
  
  <p>I'm currently using a modified <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow noreferrer">Horowitz-Sahni</a> algorithm. For example, I first call it to for the smallest sum greater than or equal to A, giving me s<sub>1</sub>. Then I call it again for the next smallest sum greater than s<sub>1</sub>, giving me s<sub>2</sub>. Repeat this until we find a sum s<sub>k+1</sub> greater than B. There is a lot of computation repeated between each iteration, even without rebuilding the initial two 2<sup>N/2</sup> lists, so is there a way to do better?</p>
  
  <p>In my problem, N is about 15, and the magnitude of the numbers is on the order of millions, so I haven't considered the dynamic programming route.</p>