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

Question

我得到一个包含 4 个随机数（包括 1 到 10）列表的数组。我应该生成一个包含 3 个数字（包括 1 到 10）的列表，以便我可以通过添加生成列表的 3 个数字来生成初始列表的所有 4 个数字。

有人请提供这样做的算法。

Answer 1

由于该解决方案仅包含 1..10 范围内的 3 个数字，因此蛮力是一种有效的算法（即使在幼稚的实现中也最多检查 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 项列表生成。