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.

#679

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

24 点游戏

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。你须遵守以下规则: 除法运算符 '/' 表示实数除法…

数组数学回溯

题目描述

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
- 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
- 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
- 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

提示:

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

lightbulb

解题思路

方法一：DFS

我们设计一个函数 $dfs(nums)$ ，其中 $nums$ 表示当前的数字序列，函数返回一个布尔值，表示是否存在一种排列方式，使得这个数字序列可以得到 $24$ 。

如果 $nums$ 的长度为 $1$ ，那么只有当这个数字等于 $24$ 时，我们才返回 $true$ ，否则返回 $false$ 。

否则，我们可以枚举 $nums$ 中的任意两个数 $a$ 和 $b$ 作为左右两个操作数，枚举 $a$ 和 $b$ 之间的运算符 $op$ ，那么 $a\ op\ b$ 的结果就可以作为新的数字序列的一个元素，我们将其加入到新的数字序列中，并从 $nums$ 中移除 $a$ 和 $b$ ，然后递归地调用 $dfs$ 函数，如果返回 $true$ ，那么我们就找到了一种排列方式，使得这个数字序列可以得到 $24$ ，我们就返回 $true$ 。

如果枚举完所有的情况都没有返回 $true$ ，那么我们就返回 $false$ 。

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

33

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #1307 口算难题 #1467 两个盒子中球的颜色数相同的概率