'Sup everyone, I was trying to solve a problem which is pretty weird. I'm gonna make an example to explain what I'm trying to achieve.

I've got an array of uint. Given a certain number "n", how do I find the only solution which gives me the numbers added up to reach "n"? I'm talking of "the only solution" because there's only a solution to reach that number.

// This is not my array, but it's pretty similar.
// Given number: 96
// Used numbers to reach it: 32, 64

uint[] values = new uint[]
{
    1,
    2,
    4,
    8,
    16,
    32,
    64,
    128,
    256,
    512,
    1024,
    2048,
};

CodePudding user response：

Your problem is a fairly simple math equation since all your numbers are powers of 2, you are better off going to a maths website to explore those options

However, here is a brute force combinatorial generic approach for any list of numbers

Given

unit sum extensions

public static uint Sum(this IEnumerable<uint> source)
{
   uint sum = 0;
   checked
   {
      return source.Aggregate(sum, (current, v) => current   v);
   }
}

A way to get combinations

public static IEnumerable<T[]> GetCombinations<T>(T[] source)
{
   for (var i = 0; i < (1 << source.Length); i  )
      yield return source
         .Where((t, j) => (i & (1 << j)) != 0)
         .ToArray();
}

A way to filter targets

public static IEnumerable<uint[]> GetTargets(IEnumerable<uint> source, uint target) 
   => GetCombinations(source.ToArray())
      .Where(items => items.Sum() == target);

Usage

uint[] values = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, };

foreach (var found in GetTargets(values,96))
   Console.WriteLine(string.Join(", ", found));

Output

32, 64

Full Demo Here

Note if you use this with any arbitrarily sized list, expect to wait many life times for the answer