非递归算法,用于根据数字集确定所有可能的总和

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

其他信息:

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

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];
}

并Sum()在System.Linq命名空间中使用方法帮助查找所有组合的总和:

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