0588HardArrayMathBacktracking

Four Chips to Twenty-Four

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tabletop puzzle deals four numbered chips, given in cards, each showing a digit from 1 to 9.

The aim is to write an arithmetic line worth exactly 24 under these rules:

Each chip's number is used once and once only. The chips may be taken in any order.
The four numbers are joined by three operators, each chosen freely from +, -, * and /, and brackets may be placed however you like.
Division is ordinary division, not whole-number division, so a partial value such as one third is perfectly legal as long as the line finishes at 24. Dividing by zero is not allowed, and a zero can turn up as a partial value, for instance from a chip subtracted from an equal chip.
No two chips may be written side by side to make a two-digit number, and no number may be given a leading minus sign of its own.

All arithmetic is exact, and the line has to come to 24 exactly rather than close to it. Return true when such a line exists and false otherwise.

Examples

Example 1

Input: cards = [5, 5, 5, 1]
Output: true

The line 5 * (5 - 1 / 5) is worth 24, since 1 / 5 is one fifth, 5 minus one fifth is four and four fifths, and five times that is 24.

Example 2

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

Every line that can be written from four ones is worth at most 4, so 24 is out of reach.

Example 3

Input: cards = [1, 2, 3, 4]
Output: true

The line 1 * 2 * 3 * 4 is worth 24.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def judge_point24(cards: list[int]) -> bool:

Java

public boolean judgePoint24(int[] cards)

The intended approach

Time O(1) for the fixed hand of four: the search settles fewer than ten thousand states.Space O(1) — the recursion is three levels deep and each level holds at most four values.

Rather than enumerating bracket shapes, shrink the hand. Pick any two of the values in hand, in either order, replace them with the result of one of the four operations, and search again on the smaller hand. Every bracketing and every ordering of the chips is reachable that way, because any arithmetic line ends up combining two values at a time. Division is skipped when the right-hand value is zero. Values are held as exact fractions, so a partial value like one third stays exact and the final comparison against 24 needs no tolerance. A hand of one value succeeds when that value is 24.

Pythonentry point: judge_point24

def judge_point24(cards):
    # O(1) time and space for a fixed hand of four cards: repeatedly replace two
    # values by the result of one operation, which covers every bracketing and
    # every ordering, and stop as soon as a single value of exactly 24 is left.
    # Values are kept as exact fractions so no rounding can creep in.
    from fractions import Fraction

    def solve(values):
        if len(values) == 1:
            return values[0] == 24
        count = len(values)
        for i in range(count):
            for j in range(count):
                if i == j:
                    continue
                rest = [values[k] for k in range(count) if k != i and k != j]
                left = values[i]
                right = values[j]
                outcomes = [left + right, left - right, left * right]
                if right != 0:
                    outcomes.append(left / right)
                for outcome in outcomes:
                    if solve(rest + [outcome]):
                        return True
        return False

    return solve([Fraction(card) for card in cards])

The obvious version

Spell out the shapes. For every ordering of the four chips and every triple of operators, value each of the five distinct bracketings of a four-term line and check the result against 24. Values are kept as a numerator and a denominator pair of plain integers, so the check is exact, and any bracketing that divides by zero is abandoned.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_judge_point24(cards):
    from itertools import permutations, product

    def combine(a, b, op):
        an, ad = a
        bn, bd = b
        if op == 0:
            return (an * bd + bn * ad, ad * bd)
        if op == 1:
            return (an * bd - bn * ad, ad * bd)
        if op == 2:
            return (an * bn, ad * bd)
        if bn == 0:
            return None
        return (an * bd, ad * bn)

    def is24(v):
        return v is not None and v[0] == 24 * v[1]

    seen = set()
    for order in permutations(cards):
        if order in seen:
            continue
        seen.add(order)
        a = (order[0], 1)
        b = (order[1], 1)
        c = (order[2], 1)
        d = (order[3], 1)
        for o1, o2, o3 in product(range(4), repeat=3):
            step = combine(a, b, o1)
            if step is not None:
                step2 = combine(step, c, o2)
                if step2 is not None and is24(combine(step2, d, o3)):
                    return True
            step = combine(b, c, o2)
            if step is not None:
                step2 = combine(a, step, o1)
                if step2 is not None and is24(combine(step2, d, o3)):
                    return True
                step2 = combine(step, d, o3)
                if step2 is not None and is24(combine(a, step2, o1)):
                    return True
            step = combine(a, b, o1)
            other = combine(c, d, o3)
            if step is not None and other is not None:
                if is24(combine(step, other, o2)):
                    return True
            step = combine(c, d, o3)
            if step is not None:
                step2 = combine(b, step, o2)
                if step2 is not None and is24(combine(a, step2, o1)):
                    return True
    return False

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in