0679. 24 点游戏

题目地址(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 。

前置知识

• 回溯

• 数字精度问题

• 分治

公司

• 暂无

思路

题目给了我们四个数字，让我们通过 + - $\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:

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 啦。

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