1.题目基本信息

1.1.题目描述

给定一个长度为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.2.题目地址

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

2.解题方法

2.1.解题思路

回溯递归

2.2.解题步骤

第一步，递归出口，当cards中只有一个元素时，观察是否元素时24进行返回

第二步，枚举两两组合之间的运算，并进行回溯递归

3.解题代码

python3代码

EPS = 1e-9

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        # 思路：回溯递归
        n = len(cards)
        # > 递归出口，当cards中只有一个元素时，观察是否元素时24进行返回
        if n == 1:
            return abs(cards[0] - 24) < EPS
        # > 枚举两两组合之间的运算，并进行回溯递归
        for i in range(n - 1):
            for j in range(i + 1, n):
                x, y = cards[i], cards[j]
                candidates = [x + y, x - y, y - x, x * y]
                if x != 0:
                    candidates.append(y / x)
                if y != 0:
                    candidates.append(x / y)
                newCards = cards[:j] + cards[j + 1:]
                for candidate in candidates:
                    newCards[i] = candidate
                    if self.judgePoint24(newCards):
                        return True
        return False

4.执行结果