Algorithm to get which values make sum of a given number from array

Question

I don't know to search or google it so I ask it here. I have an array of integers with fixed size and exactly with this logic.

sample [1,2,4,8,16,32]

Now I am given a number for example 26. And I shall find the numbers whose sum will make this number, in this case is [2,8,16]

for a number of 20 it will be [4,16]

for 40 it is [8,32]

and for 63 it is all of these numbers [1,2,4,8,16,32]

What is the proper algorithm for that?

I know strictly that there is always this continuation that the number is double of the previous value. as well as only the numbers from the given array will sum up to the given number and each number will be used only for once or none

If it will be in C# method that takes array of ints and an int value and returns the array of ints that contains the ints that sum up this number from the given array will be preferred.

Thank you

Answer 1

As you can see, the number are base-2, which means you can easily use shift.

You could try this:

private IEnumerable<int> FindBits(int value)
{
    // check for bits.
    for (int i = 0; i < 32; i++)
    {
        // shift 1 by i
        var bitVal = 1 << i;   // you could use (int)Math.Pow(2, i); instead
        // check if the value contains that bit.
        if ((value & bitVal) == bitVal)
            // yep, it did.
            yield return bitVal;
    }
}

This method will check what bits are set and return them as an ienumerable. (which can be converted to an array of list)

---

Usage:

// find the bits.
var res = FindBits(40).ToArray();

// format it using the string.join
var str = $"[{string.Join(",", res)}]";

// present the results
Console.WriteLine(str);

Results in [8,32]

---

Extra info:

                          counter
00000001 =   1     = 1 << 0
00000010 =   2     = 1 << 1 
00000100 =   4     = 1 << 2
00001000 =   8     = 1 << 3
00010000 =  16     = 1 << 4
00100000 =  32     = 1 << 5
01000000 =  64     = 1 << 6
10000000 = 128     = 1 << 7

Instead of writing all combinations you make a for loop which does the counter.

---

Some extra non-sense:

If you like lambda's, you could replace the FindBits with this:

private Func<int, IEnumerable<int>> FindBits = (int value) => Enumerable
    .Range(0, 31)
    .Select(i => 2 << i).Where(i => (value & i) == i);

But it's better to keep it simpel/readable.