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

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