用于在列表中查找与目标相等的一组数字的算法

Question

所以这就是我想要做的.我有一个整数列表:

List<int> myList = new List<int>() {5,7,12,8,7};

我也有一个目标:

int target = 20;

我正在尝试做的是找到一种方法来创建一个新的整数列表,当它们加在一起时等于我的目标.所以,如果我的目标是20,我需要一个这样的列表:

{ 12, 8 }

如果我的目标是26,那么我将拥有:

{ 7, 12, 7 }

每个数字只能使用一次(7使用两次,因为它在列表中两次).如果没有解决方案,则应返回空列表.任何人都知道如何做这样的事情？

Answer 1

这是一个统计问题。您想要找到具有匹配总和的所有可能组合。我可以推荐这个项目，它也值得一读：

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-CG

那么就简单高效了：

List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
var allMatchingCombos = new List<IList<int>>();
for (int lowerIndex = 1; lowerIndex < myList.Count; lowerIndex++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(myList, lowerIndex, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 20);
    allMatchingCombos.AddRange(matchingCombos);
}

foreach(var matchingCombo in allMatchingCombos)
    Console.WriteLine(string.Join(",", matchingCombo));

输出：

12,8
5,7,8
5,8,7