When you’re given a bunch of random numbers that need to be sorted finding a sorting algorithm can be complex. But when you’re building the list the list of numbers yourself, all you need to do is make sure the list is ordered at each step of your program.

If, as your examples somewhat suggest, *x1+x2+x3* is a valid sum, but *x1+x3* (skipping the *x2*) is not, the problem isn’t all that hard. What you need to do is make a copy of the list, which is assumed to be ordered, and start inserting *x1+x2* (and then *x1+x2+x3*, etc) at the right place.

Any insert shouldn’t take any longer than *2n* (the lists maximal length) steps, and with *n* inserts this is a O(n^2) solution.

On the other hand, if you need to take into account sums like *x1+x3* the problem becomes harder. This is not because of the sorting requirement but because it seems like you need to generate all possible combinations of *x*’s. Each *xi* can either be in or out, so you get *2^n* possible combinations. The thing to note, however, is that it’s unlikely that there’ll also be *2^n* different outcomes. As an example, consider the inputlist consisting of just *n* copies of the number one. The outcome list will just be [*0,1,2,3,…,n*].

That’s something to take advantage of. Make sure your insert procedure handles duplicates correctly… Here’s your algorithm:

[ul]

[li] Start out with a result list consisting of just the number 0.[/li][li] To each result in the result list add x1 and insert it into the result list, which is now [*0,x1*][/li][li] To each result in the result list add x2 and insert it into the result list, which is now [*0,x1, x2, x1+x2*][/li][li] To each result in the result list add x3 and insert it into the result list, which is now [*0,x1, x2, x3, x1+x2, x1+x3, x2+x3, x1+x2+x3*] (Note that i haven’t ordered anything, nor removed duplicates. Your program *should* do both these things)[/li][li] …[/li][/ul]

(note that at each step the list of results doubles in length, so if there aren’t any duplicates you’ll end up with a list consisting of *2^n* entries, as expected)

If there are *m* possible outcomes, you’ve now made *n* steps that consist of at most *m* inserts into a list of length *m*, which makes the algorithm O(*n***m*^2).