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:
[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).