# 0679. 24 点游戏
### 题目地址(679. 24 点游戏)
### 题目描述
```
你有 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/backtrack)
* 数字精度问题
* 分治
### 公司
* 暂无
### 思路
题目给了我们四个数字，让我们通过 + - $\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 题解仓库： 。 目前已经 40K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
