679. 24 Game


You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

  1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.


b'
\n
\n\n
\n

Approach #1: Backtracking [Accepted]

\n

Intuition and Algorithm

\n

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.

\n

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.

\n

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.

\n\n

Complexity Analysis

\n
    \n
  • \n

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

    \n
    • \n
  • \n

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

    \n
    • \n
\n
\n

Analysis written by: @awice

\n
'