Non-recursive algorithm for determine all sums possible from set of numbers

Question

I'm looking for a non-recursive algorithm (preferably in C#) which will generate a list of all sums possible from a set of positive numbers.

E.g. For a set of three numbers "1,2,3" the following seven sums are possible:

1

2

3

1+2=3

1+3=4

2+3=5

1+2+3=6

The maximum set size would be around 50. I know how to approach this problem recursively, but have been limited by the call stack in the past when tackling a similar problem, so want to avoid it this time.

Answer 1

If you just need all possible sums then you can use this function.

public static IEnumerable<int> GetSums(List<int> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               (from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i]).Sum();
}

And, then just call it like that:

var result = GetSums(myList).ToList();

Additional information:

You can also use this method for generating combinations(source):

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

And find the sums of all combinations with the help of Sum() method from the System.Linq namespace:

var result = GetPowerSet(myList).Select(x => x.Sum()).ToList();