Given 4 numbers of array of 1 to 10 elements. Find 3 numbers whose sum can generate all the four numbers?

Question

I am given an array containing a list of 4 random numbers (1 to 10 inclusive). I am supposed to generate a list of 3 numbers (1 to 10 inclusive) so that I can generate all the 4 numbers of the initial list by adding the 3 numbers of the generated list.

Someone Please provide an algorithm for doing this.

Answer 1

Since the solution contains only 3 numbers which are in 1..10 range, brute force is an effective algorithm here (at most 1000 possibilities to check even in naive implementation). So C# code could be

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
}

Some test cases:

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]; same as previous case
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}); // <- No solution found

Even the problem set (all possible lists of 4 items which are in 1..10 range) is small enough (10000 items) to be solved by brute force algorithm implemented above. You can easily find out that only 768 4-items lists from 10000 can't be generated by 3-items lists.