从一组数字中确定所有可能的求和结果的非递归算法

Question

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

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

1

2

3

1+2=3

1+3=4

2+3=5

1+2+3=6

最大集大小约为50。我知道如何递归地解决这个问题，但在处理类似问题时以往曾受到调用堆栈的限制，因此这次想避免使用递归算法。

- Caustix

---

过早的优化是万恶之源。 - Rubens Farias

在最坏的情况下，有 2 ^ 50 种不同的和。或者还有其他限制可以减少它们的数量吗？顺便说一句，在递归版本中，调用深度最多为 50。我认为这不是问题。 - kraskevich

@kraskevich 不仅在最坏的情况下如此。问题中的示例表明，导致相同总和的不同组合应分别计算每个组合，因此给定 N 个数字，您将始终获得 2^N 个总和。 - user743382

这是一个很好的观点。在这个特定的例子中，实际上只有六个总数。 - Caustix

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

附加信息:

您还可以使用此方法生成组合(来源):

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

- Farhad Jabiyev

---

你的第一个函数很好用。谢谢！ 另外，我发现可以通过以下方式轻松删除重复项： var result = GetSums(myList).ToList().Distinct().ToList(); 由于列表中的第一项为零，我还需要将其删除。 - Caustix

@Caustix 很高兴能帮忙。没错，但是你不需要两次调用 ToList()。你可以使用 GetSums(myList).Distinct().ToList(); 来获取唯一值。 - Farhad Jabiyev

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值，但这将是一个长迭代。这至少可以让你开始。

- Jeremy West

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;

- MBo