#679

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

24 Game

Solve the 24 Game by arranging four card numbers using arithmetic operators and parentheses to reach exactly 24 efficiently.

array math backtracking

Problem Statement

You are given an array of four integers, each representing a card with values from 1 to 9. You must determine if you can arrange these numbers using the operators +, -, *, / and parentheses to form an expression that evaluates exactly to 24.

Return true if such an arrangement exists, otherwise return false. All standard arithmetic rules apply, including order of operations, and divisions must account for non-integer results. Use backtracking to explore combinations and prune impossible paths efficiently.

Examples

Example 1

Input: cards = [4,1,8,7]

Output: true

(8-4) * (7-1) = 24

Example 2

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Backtracking Permutations

Generate all possible orders of the four cards. For each permutation, attempt all operator combinations between the numbers recursively, treating each intermediate result as a new target for remaining numbers.

Recursive Combination with Pruning

At each recursion step, combine two numbers with an operator, replace them with the result, and recurse with the smaller set. Immediately discard combinations that cannot lead to 24, reducing unnecessary computation.

Floating-Point Precision Handling

Since division may produce fractions, compare computed values with 24 using a small epsilon to account for floating-point errors. This ensures valid expressions are not missed due to minor numerical inaccuracies.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The solution explores all permutations of four numbers (4!) and all possible operator placements recursively. Each recursion reduces the problem size, but the branching factor creates up to dozens of computations, making it O(1) in practice for fixed 4-card inputs. Space complexity is O(n) due to recursion stack and temporary arrays, manageable because n is fixed at 4.

What Interviewers Usually Probe

Candidate should quickly identify the backtracking pattern and pruning opportunities.
Expectations include correct handling of floating-point divisions and operator combinations.
Look for recognition of permutation generation and early termination to improve efficiency.

Common Pitfalls or Variants

Common pitfalls

Not considering all permutations of cards leads to missed solutions.
Ignoring floating-point precision in divisions may produce incorrect false negatives.
Failing to prune impossible intermediate results increases recursion depth unnecessarily.

Follow-up variants

Extend to n cards aiming for a target value other than 24.
Restrict operations to only addition and multiplication to simplify search space.
Include negative numbers or zeros to test robustness of recursive combination logic.

FAQ

What is the main strategy for solving the 24 Game problem?

Use backtracking to explore all permutations of the four cards, applying each arithmetic operator recursively while pruning paths that cannot reach 24.

Do I need to consider floating-point errors in 24 Game calculations?

Yes, when performing division, compare results with 24 using a small epsilon to account for floating-point precision errors.

Can I solve the 24 Game without generating all permutations?

Skipping permutations may miss valid expressions, so generating all orderings of the cards is necessary for completeness.

What is a common pitfall when backtracking for 24 Game?

A common mistake is failing to prune combinations early, which increases recursion unnecessarily and may slow down the solution.

Are there variants of 24 Game that change its backtracking approach?

Yes, variants include using more cards, different target numbers, or restricting operators, each affecting pruning and recursion logic.

terminal

Solution

Solution 1: DFS

We design a function $dfs(nums)$, where $nums$ represents the current number sequence. The function returns a boolean value indicating whether there exists a permutation that makes this number sequence equal to $24$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def dfs(nums: List[float]):
            n = len(nums)
            if n == 1:
                if abs(nums[0] - 24) < 1e-6:
                    return True
                return False
            ok = False
            for i in range(n):
                for j in range(n):
                    if i != j:
                        nxt = [nums[k] for k in range(n) if k != i and k != j]
                        for op in ops:
                            match op:
                                case "/":
                                    if nums[j] == 0:
                                        continue
                                    ok |= dfs(nxt + [nums[i] / nums[j]])
                                case "*":
                                    ok |= dfs(nxt + [nums[i] * nums[j]])
                                case "+":
                                    ok |= dfs(nxt + [nums[i] + nums[j]])
                                case "-":
                                    ok |= dfs(nxt + [nums[i] - nums[j]])
                            if ok:
                                return True
            return ok

        ops = ("+", "-", "*", "/")
        nums = [float(x) for x in cards]
        return dfs(nums)

Continue Practicing

#996 number of squareful arrays #1307 verbal arithmetic puzzle #1467 probability of a two boxes having the same number of distinct balls