Skip to main content
2 of 4
added 461 characters in body
Will Ness
  • 1k
  • 1
  • 8
  • 25

This is bad. You calculate them all first, and only then print them out. And what if n = 20, or 42, or 100? The printout will never start (and the memory will blow up before that, too).

Instead, have your program create n nested loops at run-time, in effect enumerating the binary encoding of n, and print the sums out from the innermost loop. In pseudocode:

 // {5, 4, 3}
 sum = 0
 for x in {5, 0}:   // included, not included
     sum += x
     for x in {4, 0}:
         sum += x
         for x in {3, 0}:
             sum += x
             print sum
             sum -= x
         sum -= x
     sum -= x

You can emulate the loops creation with recursion, coding only one recursive function. Pass it the array ({5, 4, 3} in your example) and a zero-based index, and work as shown above with x in {arr[i], 0}, making the recursive call with i+1, if i is in bounds (i < n); or print the sum value out, otherwise. The for loop can be inlined away as well, since there always are only two numbers to process, arr[i] and 0.

You did say print. Storing them is an insanely ginormous overkill.

edit: Thus concludes the algorithmic review, which you did request. No point to reviewing the code when algorithm is unsuitable for the task. Exponential space algorithms are never good when there's a linear space algorithm to be had.

Will Ness
  • 1k
  • 1
  • 8
  • 25