arrays - 给定 4 个包含 1 到 10 个元素的数组。找到 3 个数字，其和可以生成所有 4 个数字？

Question

给我一​​个数组，其中包含 4 个随机数(包括 1 到 10)的列表。我应该生成一个包含 3 个数字(1 到 10)的列表，这样我就可以通过添加生成列表的 3 个数字来生成初始列表的所有 4 个数字。

有人请提供执行此操作的算法。

Answer 1

由于解决方案仅包含 3 个在 1..10 范围内的数字，因此需要暴力破解 是一个有效的算法(即使在简单的实现中也最多检查 1000 种可能性)。所以 C# 代码可能是

public static int[] BruteForce(int[] data) {
  HashSet<int> hs = new HashSet<int>();

  for (int x = 1; x <= 10; ++x)
    for (int y = x; y <= 10; ++y)
      for (int z = y; z <= 10; ++z) {
        hs.Clear();

        for (int i = 0; i < data.Length; ++i)
          hs.Add(data[i]);

        hs.Remove(x);
        hs.Remove(y);
        hs.Remove(z);

        hs.Remove(x + y);
        hs.Remove(x + z);
        hs.Remove(y + z);

        hs.Remove(x + y + z);

        if (hs.Count <= 0) 
          return new int[] { x, y, z }; // <- Solution
      }

  return new int[] {}; // <- No solution found
}

一些测试用例:

1. BruteForce(new int[] {1, 3, 7, 8});//<- [1, 2, 5]
2. BruteForce(new int[] {1, 3, 7, 9});//<- [1, 2, 6]
3. BruteForce(new int[] {1, 6, 7, 9});//<- [1, 2, 6];与之前的情况相同
4. BruteForce(new int[] {4, 6, 7, 9});//<- [1, 3, 6]
5. BruteForce(new int[] {5, 6, 7, 9});//<- [2, 3, 4]
6. BruteForce(new int[] {1, 2, 4, 8});//<- 未找到解决方案

即使是问题集(1..10范围内的4个项目的所有可能列表)也是 足够小(10000 个项目)，可以通过上面实现的强力算法来解决。你 可以很容易地发现，10000个列表中只有768个4项列表不能由3项列表生成。