在一组数字中，寻找一个组合使得它们的总和等于一个已知数字的高效算法

Question

假设有一组数字：

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

- Ben

---

这是子集和问题：http://zh.wikipedia.org/wiki/%E5%AD%90%E9%9B%86%E5%92%8C%E9%97%AE%E9%A2%98 - mbeckish

这个问题本周早些时候已经被问过了。 - user703016

可能是重复的问题：算法以找出长度为n的列表中哪些数字相加等于另一个数字 - mbeckish

Answer 1

您可以使用递归。对于集合中的任意给定数字，找到加起来等于该数字的较小数字的组合：

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

用法：

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,

- Guffa

---

如何修改此解决方案以获取重复数字，例如：5,5,5,3或2,2,2,2,2,2,2,2,2？ - Kelum

@kelumpriyadarshane 在递归调用中，不要初始化和传递 int[] possible，而是直接传递 set。 - Steve Harris

应该将 n <= sum 改为 n <= left 吗？ - WAKU

Answer 2

一种可能的替代方法。对于像这样的小集合，您可以使用暴力破解。您的集合{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}有10个元素，每个元素可以存在或不存在。这可以映射到一个二进制数，介于0（= 0b0000000000）和1023（= 0b1111111111）之间。循环遍历从0到1023（包括）的数字，并检查与数字的二进制表示中设置位对应的子集的总和。

也许不是针对此特定问题最有用的方法，但它是生成给定集合的所有可能子集的好方法。

- rossum

---

你能解释一下1023吗？如何找到1023这个高度数字进行检查？ - Krishna Karki

问题中有十个数字：1、2、3、……10。这十个数字中的每一个都可以包含在结果中（1），也可以从结果中排除（0）。使用0000000000表示所有数字都被排除，使用1111111111表示所有数字都被包含。其他可能的结果在这两者之间，例如：1001010011。现在将所有可能的结果表示为二进制数。0b0000000000 = 0，0b1111111111 = 1023。这就是1023来自的地方：（2^10）-1。对于要检查的12个数字的问题，请使用（2^12）-1 = 4095。 - rossum