CODEWITHSUNDEEP
c#algorithmmathrecursionset
Caustix
Caustix

Reputation: 571

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

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.

Upvotes: 4

Views: 1215

Answers (3)

MBo
MBo

Reputation: 80187

If sum of all numbers is limited by reliable value, then DP solution exists with complexity O(N * MaxSum), else there are O(2^N) possible sums.

DP solution (Delphi):

procedure GenerateAllSums(const A: array of Integer);
var
  ASums: array of Boolean;
  S, i, j: Integer;
begin
  //find maximal possible sum
  S := 0;
  for i := 0 to High(A) do
    S := S + A[i];
  //make array for possible sums
  SetLength(ASums, S + 1);
  ASums[0] := True; // all others - false

  for i := 0 to High(A) do
    for j := S - A[i] downto 0 do
      if ASums[j] then
        ASums[j + A[i]] := True;
  //Now 'True' elements of ASums denote possible sum values
end;

Upvotes: 0

Farhad Jabiyev
Farhad Jabiyev

Reputation: 26635

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();

Upvotes: 5

Jeremy West
Jeremy West

Reputation: 12685

Sums from subsets are in direct correspondence with subsets, which are also in direct correspondence with binary sequences. If you have five items in your set, you want to iterate over all bit sequences from 00000 to 11111. Equivalently, you want to iterate from 0 to 2^5-1. If a bit is set to one, you should include the value in the sum. So, something like this:

for i = 0 to 2^n-1
  sum = 0
  for j = 0 to n - 1
    if i & (1 << j) then 
      sum += items[j]
  yield return sum

Obviously, this is pseudocode and doesn't deal with values of n larger than the number of bits used by i, but that is going to be a long iteration. This should at least get you started.

Upvotes: 4

Related Questions