24 Game: Backtracking with Arithmetic Expressions

You are given an array of four integers, each between 1 and 9. Your task is to determine whether you can use the four basic arithmetic operations (addition, subtraction, multiplication, division) and parentheses to combine all four numbers into an expression that evaluates to exactly 24. Each number must be used exactly once. This is LeetCode 679: 24 Game.

The recursive reduction approach

The key insight is that you do not need to generate full expressions with parentheses. Instead, you can think of the problem as repeatedly reducing the list of numbers. At each step, pick any two numbers from the current list, combine them with one of the four operations, and replace the pair with the result. This shrinks the list by one. Repeat until you have a single number, then check if that number equals 24.

This naturally leads to backtracking. For a list of n numbers, you try all possible pairs (order matters for subtraction and division), all four operations, and recurse on the resulting list of n-1 numbers. If any path produces 24, you return true.

Because division is involved, you need to work with floating point numbers. When checking if the final result equals 24, use an epsilon comparison (something like abs(result - 24) is less than 1e-6) to handle precision issues.

There is one subtlety: division by zero. When the divisor is zero (or very close to zero), skip that operation. This is easily handled with a guard before computing the division.

The solution

def judge_point24(cards):
    if len(cards) == 1:
        return abs(cards[0] - 24) < 1e-6

    for i in range(len(cards)):
        for j in range(len(cards)):
            if i == j:
                continue

            remaining = []
            for k in range(len(cards)):
                if k != i and k != j:
                    remaining.append(cards[k])

            for op in range(4):
                if op == 0:
                    remaining.append(cards[i] + cards[j])
                elif op == 1:
                    remaining.append(cards[i] - cards[j])
                elif op == 2:
                    remaining.append(cards[i] * cards[j])
                elif op == 3:
                    if abs(cards[j]) < 1e-9:
                        continue
                    remaining.append(cards[i] / cards[j])

                if judge_point24(remaining):
                    return True

                remaining.pop()

    return False

Walking through an example

Starting with [4, 1, 8, 7], one winning path works like this. Pick 8 and 4, subtract to get 8 - 4 = 4. The list becomes [4, 1, 7]. Next pick 7 and 1, subtract to get 7 - 1 = 6. The list becomes [4, 6]. Finally, multiply 4 * 6 = 24. That matches the target, so the answer is true.

The full expression is (8 - 4) * (7 - 1) = 4 * 6 = 24. The backtracking algorithm finds this by exhaustively exploring pair choices and operations at each level of recursion. Most paths fail, but only one needs to succeed.

Complexity

The input is always exactly 4 numbers. At the first level, there are at most 4 * 3 = 12 ordered pairs and 4 operations, giving 48 branches. At the next level with 3 numbers, there are 3 * 2 * 4 = 24 branches. Then 2 * 1 * 4 = 8. The total number of paths is bounded by 48 * 24 * 8 = 9216, which is a constant. Both time and space are O(1) because the input size is fixed.

Edge cases

• All same numbers: e.g., [8, 8, 8, 8] where 8 / (8 - 8/8) is not valid since 8/8 = 1 and 8 - 1 = 7, then 8/7 is not 24. Some same-number inputs are solvable (like [1, 5, 5, 5] where 5 * (5 - 1/5) = 24) and some are not.
• Division by zero: when a computed intermediate result is zero, the algorithm must skip division by that value. The epsilon guard on the divisor handles this.
• Floating point precision: operations like 8 / (3 - 8/3) produce results through intermediate fractions. Using an epsilon of 1e-6 for the final comparison avoids false negatives from rounding.
• Non-commutativity of subtraction and division: the algorithm must try both orderings for each pair. a - b and b - a are different, and so are a / b and b / a. Using ordered pairs (iterating i and j separately) ensures both directions are covered.

The building blocks

Exhaustive pair selection

The core pattern is picking two elements from a list, combining them, and recursing on the reduced list. This is different from the typical "choose an element" backtracking pattern. Here, you choose a pair and an operation, which creates a richer branching factor but the same structural recursion.

Floating point comparison with epsilon

Whenever a problem involves division or fractional arithmetic, exact equality checks break. Using abs(result - target) with a small epsilon is a standard technique. The choice of epsilon (here 1e-6) should be small enough to avoid false positives but large enough to absorb accumulated floating point drift.

Reduction-based recursion

Instead of building an expression tree and evaluating it, this approach reduces the problem size by one at each step. This avoids the complexity of generating all possible parenthesizations. The reduction viewpoint turns a combinatorial expression problem into a simpler "pick two, combine, recurse" pattern that is easy to implement and reason about.

From understanding to recall

The 24 Game is a clean example of reduction-based backtracking. The key idea to internalize is the "pick two, combine, recurse" loop, not any formula or closed-form expression. You need to remember three things: iterate over all ordered pairs, try all four operations (with a division-by-zero guard), and check for 24 with epsilon comparison when one number remains.

This pattern of reducing a list by combining two elements is reusable beyond this specific problem. Once you can write the pair-selection loop and the recursive structure from memory, the rest is just plugging in the right operations and base case. Spaced repetition helps you lock in that loop structure so it comes out automatically under interview pressure.

Related posts

• Generate Parentheses - Another backtracking problem where you build expressions by making constrained recursive choices
• Combination Sum - Classic backtracking with pruning, where you explore candidates and recurse on a reduced target
• Permutations - The foundational backtracking pattern for exploring all orderings, which the 24 Game extends to pairs