用于从一组数字中确定所有可能的和的非递归算法

Question

我正在寻找一种非递归算法（最好是在 C# 中），它将生成一组正数的所有可能和的列表。

例如对于一组三个数字“1,2,3”，可能有以下七个和：

1

2

3

1+2=3

1+3=4

2+3=5

1+2+3=6

最大集合大小将在50左右。我知道如何递归解决这个问题，但过去在处理类似问题时受到调用堆栈的限制，所以这次想避免它。

Answer 1

如果你只需要所有可能的总和，那么你可以使用这个函数。

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

然后，就这样称呼它：

var result = GetSums(myList).ToList();

附加信息:

您也可以使用此方法生成组合(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];
}

并借助 System.Linq 命名空间中的 Sum() 方法求出所有组合的总和：

var result = GetPowerSet(myList).Select(x => x.Sum()).ToList();

Answer 2

子集的和与子集直接对应，子集也与二进制序列直接对应。如果您的集合中有五个项目，您想要迭代从 00000 到 11111 的所有位序列。等效地，您想要从 0 迭代到 2^5-1。如果某位设置为 1，则应将该值包括在总和中。所以，像这样：

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

显然，这是伪代码，不处理大于 i 使用的位数的 n 值，但这将是一次长时间的迭代。这至少应该让你开始。

Answer 3

如果所有数字的总和受到可靠值的限制，则存在复杂度为 O(N * MaxSum) 的 DP 解决方案，否则有 O(2^N) 种可能的总和。

DP方案(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;

用于从一组数字中确定所有可能的和的非递归算法

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

c#

algorithm

math

recursion

set