24 Game — Hard Problem & Solution

Problem statement

You hold four cards, each showing a number from 1 to 9. Decide whether you can combine all four numbers, each used exactly once, with +, -, *, / and any parentheses, into an expression whose value is exactly 24.

Rules:

• / is real division, not integer division: 4 / (1 - 2 / 3) = 12.
• Every operator is binary; - cannot be used to negate a single number (-1 - 1 - 1 - 1 is not allowed).
• Numbers cannot be glued together: cards 1 and 2 cannot form 12.

Return true if 24 can be reached.

Example 1

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

Example 2

Input: cards = [1,2,1,2]
Output: false

Example 3

Input: cards = [3,3,8,8]
Output: true
Explanation: 8 / (3 - 8 / 3) = 24 — it needs a fraction along the way.

Constraints

• cards.length == 4
• 1 <= cards[i] <= 9

How to solve 24 Game

Search over the order in which numbers are merged. With exact fractions there is no rounding, so the check at the end is a plain integer comparison.

Approach

1. Represent each card as the fraction card / 1.
2. solve(list): if one fraction n / d is left, return n == 24 * d.
3. Otherwise, for every pair i < j, build the list without them and append, in turn, each combination: sum, both differences, product, and both quotients whose divisor is non-zero. Recurse; succeed if any branch does.

Why it works

Every fully parenthesised expression is a binary tree, and evaluating it bottom-up merges two values at a time — so some sequence of pair merges reproduces any expression, and the search tries them all. Fractions a/b ± c/d = (ad ± bc)/bd, (a/b)(c/d) = ac/bd, (a/b)/(c/d) = ad/bc are exact, and with four cards up to 9 the numerators and denominators stay small integers.

Complexity

• Time — O(1) — at most 6 · 6 · 3 · 6 · 1 · 6 ≈ 3,900 leaves
• Space — O(1)

Pitfalls

• Integer division gives wrong answers: [3,3,8,8] needs 8 / 3.
• Comparing doubles with == fails on values like 24.000000000000004; use fractions or an epsilon.
• Subtraction and division are not symmetric — try both orders for every pair.

Reference solution

Python

from typing import List

def judgePoint24(cards: List[int]) -> bool:
    def solve(fr):
        if len(fr) == 1:
            return fr[0][0] == 24 * fr[0][1]
        k = len(fr)
        for i in range(k):
            for j in range(i + 1, k):
                rest = [fr[t] for t in range(k) if t != i and t != j]
                a, b = fr[i]
                c, d = fr[j]
                cand = [(a * d + c * b, b * d), (a * d - c * b, b * d), (c * b - a * d, b * d), (a * c, b * d)]
                if c != 0:
                    cand.append((a * d, b * c))
                if a != 0:
                    cand.append((c * b, d * a))
                for f in cand:
                    if solve(rest + [f]):
                        return True
        return False

    return solve([(v, 1) for v in cards])

JavaScript

var judgePoint24 = function(cards) {
    var solve = function(nums, dens) {
        var k = nums.length;
        if (k === 1) return nums[0] === 24 * dens[0];
        for (var i = 0; i < k; i++) {
            for (var j = i + 1; j < k; j++) {
                var rn = [], rd = [];
                for (var t = 0; t < k; t++) if (t !== i && t !== j) { rn.push(nums[t]); rd.push(dens[t]); }
                var a = nums[i], b = dens[i], c = nums[j], d = dens[j];
                var cn = [a * d + c * b, a * d - c * b, c * b - a * d, a * c];
                var cd = [b * d, b * d, b * d, b * d];
                if (c !== 0) { cn.push(a * d); cd.push(b * c); }
                if (a !== 0) { cn.push(c * b); cd.push(d * a); }
                for (var x = 0; x < cn.length; x++) {
                    rn.push(cn[x]);
                    rd.push(cd[x]);
                    if (solve(rn, rd)) return true;
                    rn.pop();
                    rd.pop();
                }
            }
        }
        return false;
    };
    return solve(cards.slice(), [1, 1, 1, 1]);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• Verbal Arithmetic Puzzle Hard
• Distribute Repeating Integers Hard