LeetCode 679: 24 Game

Problem Restatement

We are given exactly four cards.

Each card contains an integer from 1 to 9.

We need to decide whether we can arrange all four numbers into a mathematical expression that evaluates to 24.

We may use:

There are also important restrictions:

The official examples include cards = [4,1,8,7], which returns true because (8 - 4) * (7 - 1) = 24, and cards = [1,2,1,2], which returns false.

Input and Output

Example function shape:

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

Examples

Example 1:

cards = [4, 1, 8, 7]

One valid expression is:

(8 - 4) * (7 - 1)

This gives:

4 * 6 = 24

Answer:

True

Example 2:

cards = [1, 2, 1, 2]

There is no valid way to combine all four cards with the allowed operations to get 24.

Answer:

False

Example 3:

cards = [3, 3, 8, 8]

One valid expression is:

8 / (3 - 8 / 3)

This gives:

8 / (1 / 3) = 24

Answer:

True

This example shows why real division matters.

First Thought: Enumerate Expressions

A direct idea is to try every possible expression.

We could choose an ordering of the four numbers, choose operations between them, and choose parenthesization.

This is possible because there are only four cards, but writing expression generation directly is awkward.

Parentheses create many cases:

((a op b) op c) op d
(a op (b op c)) op d
a op ((b op c) op d)
a op (b op (c op d))
(a op b) op (c op d)

A cleaner way is to think recursively.

Instead of building strings, we repeatedly choose two numbers, combine them with one operation, and put the result back.

Each operation reduces the list size by one.

Starting with four numbers:

[a, b, c, d]

After one operation:

[x, c, d]

After another operation:

[y, d]

After the last operation:

[z]

If z is close to 24, we return true.

Key Insight

Every valid expression can be represented as a sequence of binary operations.

Each operation takes two current numbers and replaces them with the result.

For example:

(8 - 4) * (7 - 1)

can be viewed as:

[4, 1, 8, 7]
choose 8 and 4 -> 4
choose 7 and 1 -> 6
choose 4 and 6 -> 24

So we do not need to explicitly generate parentheses.

The recursion over pairs already covers all possible parenthesizations.

Algorithm

Use depth-first search.

Given a list of current numbers:

1. If the list has one number, check whether it is close to 24.
2. Otherwise, choose every pair of numbers.
3. For each pair (a, b), generate all possible results:
   • a + b
   • a - b
   • b - a
   • a * b
   • a / b, if b != 0
   • b / a, if a != 0
4. For each result, form the next list:
   • remove a and b
   • add the result
5. Recurse on the next list.
6. If any recursive path reaches 24, return true.
7. If none work, return false.

We use floating-point numbers because division can produce fractions.

We compare with a tolerance, not exact equality.

abs(value - 24) < 1e-6

Walkthrough

Consider:

cards = [4, 1, 8, 7]

One successful recursive path is:

[4, 1, 8, 7]

Choose 8 and 4.

8 - 4 = 4

Next state:

[1, 7, 4]

Choose 7 and 1.

7 - 1 = 6

Next state:

[4, 6]

Choose 4 and 6.

4 * 6 = 24

Next state:

[24]

The only remaining number is 24, so the answer is true.

Correctness

Every recursive step chooses two current numbers and applies one binary operation to them.

This matches the problem rules because every allowed operation is binary.

The algorithm never creates a number without using existing numbers. It only replaces two existing values by the result of applying one allowed operation. Therefore, every recursive state represents some expression built from the original cards.

When the list has one number, that number is the value of an expression using all four cards exactly once.

If it is equal to 24 within a small tolerance, the algorithm correctly returns true.

Now suppose there exists some valid expression that evaluates to 24.

The root operation of that expression combines two subexpressions. The algorithm tries every possible pair of current values and every allowed operation, so it can choose the same root operation at some recursive step.

The same argument applies recursively to the subexpressions.

Therefore, the algorithm explores a path corresponding to that valid expression and returns true.

If the algorithm returns false, it has exhausted all possible ways to repeatedly combine two numbers with the allowed operations. Since every valid expression has exactly this binary-operation structure, no valid expression can produce 24.

Complexity

The input size is fixed at four cards, so the practical running time is constant.

More generally, if there are n numbers, the recursion chooses pairs at each level.

For each pair, we try a constant number of operation results.

So the search space is exponential in n.

For this problem, n = 4, so the algorithm is small and fast.

If generalized to variable n, the depth is O(n), and the number of states grows exponentially.

Implementation

class Solution:
    def judgePoint24(self, cards: list[int]) -> bool:
        nums = [float(card) for card in cards]
        return self._can_make_24(nums)

    def _can_make_24(self, nums: list[float]) -> bool:
        eps = 1e-6

        if len(nums) == 1:
            return abs(nums[0] - 24.0) < eps

        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                a = nums[i]
                b = nums[j]

                rest = []
                for k in range(n):
                    if k != i and k != j:
                        rest.append(nums[k])

                candidates = [
                    a + b,
                    a - b,
                    b - a,
                    a * b,
                ]

                if abs(b) > eps:
                    candidates.append(a / b)

                if abs(a) > eps:
                    candidates.append(b / a)

                for value in candidates:
                    if self._can_make_24(rest + [value]):
                        return True

        return False

Code Explanation

We first convert cards to floating-point numbers:

nums = [float(card) for card in cards]

This is needed because division can create non-integer values.

The recursive helper receives the current list of numbers:

def _can_make_24(self, nums: list[float]) -> bool:

If only one number remains, we check whether it is close to 24:

if len(nums) == 1:
    return abs(nums[0] - 24.0) < eps

We use eps because floating-point arithmetic can produce tiny rounding errors.

Then we try every pair:

for i in range(n):
    for j in range(i + 1, n):

Using i + 1 avoids choosing the same pair twice.

For each pair, we collect the unused numbers:

rest = []
for k in range(n):
    if k != i and k != j:
        rest.append(nums[k])

Then we generate every result from combining a and b.

Addition and multiplication are commutative, so one direction is enough:

a + b
a * b

Subtraction and division are not commutative, so we need both directions:

a - b
b - a
a / b
b / a

Before division, we avoid dividing by zero:

if abs(b) > eps:
    candidates.append(a / b)

Finally, we recurse with the new value added back:

if self._can_make_24(rest + [value]):
    return True

If any path works, the answer is true.

If no pair and no operation leads to 24, return false.

Testing

def run_tests():
    s = Solution()

    assert s.judgePoint24([4, 1, 8, 7]) is True
    assert s.judgePoint24([1, 2, 1, 2]) is False
    assert s.judgePoint24([3, 3, 8, 8]) is True
    assert s.judgePoint24([1, 1, 1, 1]) is False
    assert s.judgePoint24([7, 7, 7, 7]) is True
    assert s.judgePoint24([1, 5, 5, 5]) is True

    print("all tests passed")

run_tests()

Test meaning: