C# 在一组数字中找到总和等于已知数字的组合的有效算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10738926/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number
提问by Ben
Let's say there is a set of number
假设有一组数字
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
I want to find out several combinations in the set of number such that the summation of it equal to a known number, for example, 18. We can find out that 5, 6, 7 is matched (5+6+7=18).
我想找出一组数字中的几种组合，使其总和等于一个已知数字，例如，18。我们可以找到匹配的 5, 6, 7 (5+6+7=18) .
Numbers in a combination cannot be repeated and the number in a set may not be consecutive.
组合中的数字不能重复，一组中的数字不能连续。
I've wrote a C# program to do that. The program is random to pick up number to form a combination and check whether the summation of combination is equal to a known number. However, the combination the program found may be repeated and it makes the progress not effective.
我写了一个 C# 程序来做到这一点。程序随机取数组成组合，并检查组合之和是否等于已知数。但是，程序找到的组合可能会重复，从而使进度无效。
I am wondering whether there is any efficient algorithm to find out such combination.
我想知道是否有任何有效的算法来找出这种组合。
Here's part of my code.
这是我的代码的一部分。
int Sum = 0;
int c;
List<int> Pick = new List<int>();
List<int> Target = new List<int>() {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 < Pick.Count; i++)
Sum += Set[Pick[i]];
if (Sum >= Target[Target.Count - 1])
break;
}
}
Result.Add(Pick);
采纳答案by Guffa
You can use recursion. For any given number in the set, find the combinations of smaller numbers that adds up to the number:
您可以使用递归。对于集合中的任何给定数字，找出与该数字相加的较小数字的组合：
public static IEnumerable<string> 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;
}
}
}
}
}
Usage:
用法：
int[] set = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
foreach (string s in GetCombinations(set, 18, "")) {
Console.WriteLine(s);
}
Output:
输出：
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,
回答by rossum
A possible alternative method. With a small set like this, you could use brute force. Your set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}has 10 elements, and each element can be present or not present. That can be mapped to a binary number between 0 (= 0b0000000000) and 1023 (= 0b1111111111). Loop through the numbers from 0 to 1023, inclusive, and check the sum for the subset corresponding to the set bits of the binary representation of the number.
一种可能的替代方法。像这样的小集合，你可以使用蛮力。你的集合{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}有 10 个元素，每个元素可以存在或不存在。这可以映射到 0 (= 0b0000000000) 和 1023 (= 0b1111111111) 之间的二进制数。循环遍历从 0 到 1023（含）的数字，并检查与该数字的二进制表示的设置位对应的子集的总和。
Maybe not the most useful for this particular question, but a good way to generate all possible subsets of a given set.
对于这个特定问题，可能不是最有用的方法，而是生成给定集合的所有可能子集的好方法。
