Approach #1: Backtracking [Accepted]

Intuition and Algorithm

There are only 4 cards and only 4 operations that can be performed. Even when all operations do not commute, that gives us an upper bound of possibilities, which makes it feasible to just try them all. Specifically, we choose two numbers (with order) in 12 ways and perform one of 4 operations (12 * 4). Then, with 3 remaining numbers, we choose 2 of them and perform one of 4 operations (6 * 4). Finally we have two numbers left and make a final choice of 2 * 4 possibilities.

We will perform 3 binary operations (+, -, *, / are the operations) on either our numbers or resulting numbers. Because - and / do not commute, we must be careful to consider both a / b and b / a.

For every way to remove two numbers a, b in our list, and for each possible result they can make, like a+b, a/b, etc., we will recursively solve the problem on this smaller list of numbers.

Complexity Analysis

  • Time Complexity: . There is a hard limit of 9216 possibilities, and we do work for each of them.

  • Space Complexity: . Our intermediate arrays are at most 4 elements, and the number made is bounded by an factor.


Analysis written by: @awice