find numbers that can be formed from sum of numbers from array in ascending order

Question

I am trying to find the all possible values which are result of sum of values of given array. For example if given array is a = [50,100,120,260,360] then result will be [0,50,100,120,150,170,200,220,240,250,260,....]. How to implement it ?

I found one article realted to it but that is about to find the value which can't be formed using given array.

Find smallest number which can't be formed by values of given array

I found one more discussion related to something this but it is all about mathematics and I am still unable to understand how to implement it. You can have a look at it Find all possible values which can be formed using some values

Any algorithm or any code in C# could help.

Edit

We can use a single value many times.

more results could be 270 (50*1 + 100*1 + 120) , 300 (100*3), 310 (50 * 1 + 260 *1) etc.

Shouldn't there be more values in the results, like 280, and 360. — juharr, Oct 10 '15 at 04:00
@paulpaul1076 : I need to find all possible values which can be formed by addition of one or more values from given array. We can use a single value of array multiple times. — Vishal Goyal, Oct 10 '15 at 04:19
If you can use any element any number of times, doesn't that lead to an infinite number of possibilities? — i_am_jorf, Oct 10 '15 at 04:42
@i_am_jorf : We can take the value from the user like how many numbers he require. — Vishal Goyal, Oct 10 '15 at 04:45
Why don't you go ahead and just post all of the requirements? :) — i_am_jorf, Oct 10 '15 at 04:47

Enigmativity · Accepted Answer · 2015-10-10T06:30:47.880

This is what I use:

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null;
getAllSubsets = xs =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        : xs.Skip(1).Any()
            ? getAllSubsets(xs.Skip(1))
                .SelectMany(ys => new[] { ys, xs.Take(1).Concat(ys) })
            : new[] { Enumerable.Empty<int>(), xs.Take(1) };

Then you can do this:

var a = new [] { 50, 100, 120, 260, 360 };

Console.WriteLine(String.Join(", ", getAllSubsets(a).Select(x => x.Sum()).OrderBy(x => x)));

I get this:

0, 50, 100, 120, 150, 170, 220, 260, 270, 310, 360, 360, 380, 410, 410, 430, 460, 480, 480, 510, 530, 530, 580, 620, 630, 670, 720, 740, 770, 790, 840, 890

Knowing that values can be repeated then this is a way to go:

public IEnumerable<int> GenerateAllSums(int[] array)
{
    var buffer = new LinkedList<int>();
    buffer.AddFirst(0);
    while (true)
    {
        var first = buffer.First;
        var nexts = array.Select(a => first.Value + a);
        foreach (var next in nexts)
        {
            var x = buffer.First;
            while (x.Value < next)
            {
                x = x.Next;
                if (x == null)
                {
                    break;
                }
            }
            if (x == null)
            {
                buffer.AddLast(next);
            }
            else if (x.Value != next)
            {
                buffer.AddBefore(x, next);
            }
        }
        buffer.RemoveFirst();
        yield return first.Value;
    }
}

I can call it like so:

var a = new [] { 50, 100, 120, 260, 360, };

Console.WriteLine(String.Join(", ", GenerateAllSums(a).Take(100)));

It's important to note that the .Take(...) is now vital as the sequence is infinite.

Given the .Take(100) I get this result:

0, 50, 100, 120, 150, 170, 200, 220, 240, 250, 260, 270, 290, 300, 310, 320, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 1000, 1010, 1020, 1030, 1040, 1050, 1060, 1070, 1080, 1090, 1100, 1110, 1120, 1130, 1140, 1150, 1160, 1170

:Thank You sir. It is something related to my problem. The only difference is in this solution we are not using value multiple times. We are using each given value only once. — Vishal Goyal, Oct 10 '15 at 05:02
@VishalGoyal - Mine only uses each value once. Why do you think it uses values multiple times? — Enigmativity, Oct 10 '15 at 05:04
Sir that is I am saying. In your solution you are using each value once while we can use values multiple times as per our requirement. :D — Vishal Goyal, Oct 10 '15 at 05:07
I'm not sure if this is the right answer or not but I have up-voted it. Never before I saw such a dance of recursion and ternary operator. — displayName, Oct 10 '15 at 05:20
@VishalGoyal - Ah, I see. Your tense was backward in your original comment. So then the problem is that you'll have an infinite sequence. I assume that you want a breadth-first generator algorithm? — Enigmativity, Oct 10 '15 at 05:34
@displayName - Ta. It's just a logical progression to go from `IEnumerable` to `IEnumerable>` - after a bit of trial and error. :-) — Enigmativity, Oct 10 '15 at 05:35
@VishalGoyal - To do this properly I think you'll need a priority heap. — Enigmativity, Oct 10 '15 at 05:37

score 1 · Answer 2 · answered Oct 10 '15 at 04:20

Find all subset of your array using something like this then sum, you will get all the possible values if you don't need the duplicated one remove them.

 int[] source = new int[] { 50,100,120,260,360 };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     int[] combination = new int[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

`Math.Pow(2, source.Length)` can be replaced with `1 << source.Length` — Backs, Oct 10 '15 at 04:33

Miyuru Ratnayake · Answer 3 · 2015-10-10T05:22:24.657

 var repeat = 8;
 int[] source = new int[] {
     50, 100, 120, 260, 360
 };
 List < int > results = new List < int > ();
 for (int i = 0; i < Math.Pow(repeat, source.Length); i++) {
     var sum = 0;
     var bin = Convert.ToString(i, repeat);
     for (var j = 0; j < bin.Length; j++) {
         var pos = int.Parse(bin[j].ToString());
         if (0 < pos) {
             sum += source[j] * pos;
         }
     }
     results.Add(sum);
 }
 Console.WriteLine(results.Union(source).Distinct().OrderBy(x = > x));

score 0 · Answer 4 · answered Oct 10 '15 at 06:52

Here is the most efficient way to do that:

public static class Algorithms
{
    public static IEnumerable<int> AllSums(this int[] source)
    {
        var indices = new int[source.Length];
        for (int count = 0, sum = 0, next = 0; ; next++)
        {
            if (next < source.Length)
            {
                indices[count++] = next;
                sum += source[next];
                yield return sum;
            }
            else
            {
                if (count == 0) break;
                next = indices[--count];
                sum -= source[next];
            }
        }
    }
}

Sample usage:

var source = new[] { 50, 100, 120, 260, 360 };
Console.WriteLine("Source: {" + string.Join(", ", source.Select(n => n.ToString())) + "}");
Console.WriteLine("Sums: {" + string.Join(", ", source.AllSums().Select(n => n.ToString())) + "}");

or

var source = new[] { 50, 100, 120, 260, 360 };
foreach (var sum in source.AllSums())
{
    // do something with the sum
}

find numbers that can be formed from sum of numbers from array in ascending order

4 Answers4