在一组数字中找到组合的有效算法，其总和等于已知数字

本文关键字：数字 算法 有效 组合 一组 | 更新日期: 2023-09-27 18:35:24

假设有一组数字

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

在一组数字中找到组合的有效算法，其总和等于已知数字

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

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,

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

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

相关文章：