我正在寻找一种非递归算法(最好是在 C# 中),它将生成一组正数的所有可能和的列表。
例如对于一组三个数字“1,2,3”,可能有以下七个和:
1
2
3
1+2=3
1+3=4
2+3=5
1+2+3=6
最大集合大小将在 50 左右。我知道如何递归地解决这个问题,但过去在处理类似问题时受到调用堆栈的限制,所以这次想避免它。
最佳答案
如果您只需要所有可能的总和,那么您可以使用此函数。
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();
关于c# - 用于从一组数字中确定所有可能的和的非递归算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28792387/