problems/679.24-game.md · lonuslan/leetcode

## 题目地址(679. 24 点游戏)

https://leetcode-cn.com/problems/24-game/

## 题目描述

```
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

示例 1:

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

示例 2:

输入: [1, 2, 1, 2]
输出: False

注意:

除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
```

## 前置知识

- [回溯](https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md "回溯")
- 数字精度问题
- 分治

## 公司

- 暂无

## 思路

题目给了我们四个数字，让我们通过 + - $\times$ $\div$ 将其组成 24。由于题目数据范围只可能是 4，因此使用暴力回溯所有可能性是一个可行的解。

我们先使用回溯找出 nums 的全部全排列，这一步需要枚举 $4 \times 3 \times 2 \times 1$ 种可能。由于四种运算都是双目运算（题目明确指出 - 不能当成负号），因此我们可以任意选出两个，继续枚举四种运算符。 由于选出哪个对结果没有影响，因此不妨我们就选前两个。接下来，将前两个的运算结果和后面的数继续**使用同样的方法来解决**。 这样问题规模便从 4 缩小到了 3，这样不断进行下去直到得到一个数字为止。如果剩下的这唯一的数字是 24，那么我们就返回 true，否则返回 false。

值得注意的是，实数除存在精度误差。因此我们需要判断一下最后的结果离 24 不超过某个精度范围即可，比如如果结果和 24 误差不超过 $10^{-6}$，我们就认为是 24，返回 true 即可。

## 关键点

- 使用递归将问题分解成规模更小的同样问题
- 精度控制，即如果误差不超过某一个较小的数字就认为二者是相等的

## 代码

- 语言支持：Python3

Python3 Code:

```python

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return math.isclose(nums[0], 24)
        return any(self.judgePoint24([x] + rest) for a, b, *rest in permutations(nums) 
for x in [a+b, a-b, a*b, b and a/b])

```

**复杂度分析**

由于题目输入大小恒为 4 ，因此实际上我们算法复杂度也是一个定值。

- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)

lonuslan/leetcode

About

Releases

Contributors

Activities