如何通过将数字列表中的数字和 return 使用的数字相加来找到给定的数字？

Question

'大家好，我正在尝试解决一个非常奇怪的问题。我将举一个例子来解释我想要实现的目标。

我有一个 uint 数组。给定一个特定的数字“n”，我如何找到唯一的解决方案，使我的数字加起来达到“n”？我说的是“唯一的解决方案”，因为只有一个解决方案才能达到这个数字。

// 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,
};

Answer 1

你的问题是一个相当简单的数学方程式，因为你所有的数字都是 2 的幂，你最好去数学网站探索这些选项

但是，这里有一个适用于任何数字列表的强力组合通用方法

给定

单位总和扩展

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

获得组合的方法

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

一种过滤目标的方法

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

用法

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

输出

32, 64

Full Demo Here

请注意，如果您将此与任意大小的列表一起使用，则需要等待许多生命周期才能得到答案

Answer 2

如果 values 是一个数的所有幂的列表（在您的示例中，是 2 的幂）。然后你可以从后到前遍历权力列表，找到高于你打破部分的数字的值，并从数字中减去它们（一种贪婪的方法）：

private static IEnumerable<uint> FindParts(uint number, uint []powers)
{
    for (var i = powers.Length - 1; i >= 0; i--)
    {
        if (number >= powers[i])
        {
            yield return powers[i];
            number -= powers[i];
        }
    }
}

并像

一样使用它

uint randomNumber = (uint)new Random().Next(4095);
var parts = FindParts(randomNumber, values);

Console.WriteLine($"{randomNumber}={string.Join('+', parts)}");

See Live

如何通过将数字列表中的数字和 return 使用的数字相加来找到给定的数字？

How to find a given number by adding up numbers from list of numbers and return the used numbers?

c#

recursion

numbers

list

add