c# - 在列表中查找等于目标的一组数字的算法

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-C-G

然后就简单高效了:

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