title: Fastest way to get all combinations of numbers in array without gaps
body: <p>I need to calculate the sum from every possible combination of numbers in array (separate sums, not one total). Combinations cannot skip a number, so:</p>
  
  <p>For y > x you need to add every number between a[x] and a[y].</p>
  
  <p>For n-sized array you have (n)+(n-1)+(n-2)+...+1 , so for n = 5 there is 15 combinations.</p>
  
  <p>I need to do as fast as possible and space is not a problem.</p>
  
  <p>Edit: I tried:</p>
  
  <pre><code>unsigned long long r_all = 0;
  std::vector&lt;int&gt; g_seentimes(m);
  
  for(int i = 0; i&lt;n; i++)
      r_all += w[z];
      if(r_all &gt; r){
          r = r_all;
      }
  }
  
  for(int j = 0; j&lt;n; j++){
  
      unsigned long long r_temp = r_all;
  
      for(int i = 0; i&lt;(n-j); i++){
  
          r_temp -= w[n-i];
  
          if( r_temp &gt; r){
              r = r_temp;
          }
      }
  
      r_all -= w[y];
  
      if( r_all &gt; r){
              r = r_all;
      }
  
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>for(int i = 0; i &lt; n; i++){
      unsigned long long r_temp = 0;
      for(int j = 0; j&lt;(n-i); j++){
          r_temp += w[i+j];
          if(r_temp &gt; r){
              r = r_temp;
          }
      }
  }
  //r is the answer
  </code></pre>
  
  <p>Edit 2:
  Expected output is maximum possible number, BUT example i privided is simplyfied version, originally if there is two or more of same number in combination, you dont add value of any of them, so {5, 3, 5, 3, 1} = 1, but {5, 3, 1} = 9. I got that part figured out, just need the fastest possible way to get through all combinations.</p>
  
  <p>Edit 3:
  <a href="https://stackoverflow.com/users/3713927/tuan333">@Tuan333</a> Asked about number of combinations and i think it'll be easier to show it:</p>
  
  <pre><code>X- chosen, x-unchosen
  n = 5
  
  XXXXX    XXXXx    XXXxx    XXxxx    Xxxxx
  xXXXX    xXXXx    xXXxx    xXxxx
  xxXXX    xxXXx    xxXxx
  xxxXX    xxxXx
  xxxxX
  </code></pre>