在一组数中找到组合的有效算法，其总和等于已知数
假设有一组数字
1,2,3,4,5,6,7,8,9,10
我想在数字集合中找出几个组合，使得它的总和等于已知数字，例如，18。我们可以发现5,6,7是匹配的（5 + 6 + 7 = 18） 。
组合中的数字不能重复，并且集合中的数字可能不连续。
我写了一个C＃程序来做到这一点。 该程序是随机的，以获取数字以形成组合并检查组合的总和是否等于已知数。 但是，程序发现的组合可能会重复，并使进度无效。
我想知道是否有任何有效的算法来找出这样的组合。
这是我的代码的一部分。
int Sum = 0; int c; List Pick = new List(); List Target = new List() {some numbers} Target.Sort(); while (!Target.Contains(Sum)) { if (Sum > Target[Target.Count - 1]) { Pick.Clear(); Sum = 0; } while (true) { if (Pick.IndexOf(c = Math0.rand(0, Set.Count - 1)) == -1) { Pick.Add(c); } //Summation Pick Sum = 0; for (int i = 0; i = Target[Target.Count - 1]) break; } } Result.Add(Pick); 你可以使用递归。 对于集合中的任何给定数字，找到与数字相加的较小数字的组合：
public static IEnumerable GetCombinations(int[] set, int sum, string values) { for (int i = 0; i < set.Length; i++) { int left = sum - set[i]; string vals = set[i] + "," + values; if (left == 0) { yield return vals; } else { int[] possible = set.Take(i).Where(n => n <= sum).ToArray(); if (possible.Length > 0) { foreach (string s in GetCombinations(possible, left, vals)) { yield return s; } } } } }
用法：
int[] set = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; foreach (string s in GetCombinations(set, 18, "")) { Console.WriteLine(s); }
输出：
1,2,4,5,6, 3,4,5,6, 1,2,3,5,7, 2,4,5,7, 2,3,6,7, 1,4,6,7, 5,6,7, 1,2,3,4,8, 2,3,5,8, 1,4,5,8, 1,3,6,8, 4,6,8, 1,2,7,8, 3,7,8, 2,3,4,9, 1,3,5,9, 4,5,9, 1,2,6,9, 3,6,9, 2,7,9, 1,8,9, 1,3,4,10, 1,2,5,10, 3,5,10, 2,6,10, 1,7,10, 8,10,
一种可能的替代方法。 像这样的小套装，你可以使用蛮力。 你的集{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}有10个元素，每个元素都可以存在或不存在。 这可以映射到0（= 0b0000000000）和1023（= 0b1111111111）之间的二进制数。 循环遍历从0到1023（包括0和1023）的数字，并检查与数字的二进制表示的设置位对应的子集的总和。
对于这个特定问题，可能不是最有用的，但是生成给定集合的所有可能子集的好方法。