24 点游戏

难度: Hard

给定一个长度为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

Submission

运行时间: 36 ms

内存: 16.0 MB

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        if len(cards) == 1:
            return abs(cards[0] - 24) < 1e-6

        # 尝试每一种分割方式
        for i in range(len(cards)):
            for j in range(len(cards)):
                if i != j:
                    # 选择两个不同的数字
                    num1, num2 = cards[i], cards[j]
                    # 剩余的数字
                    next_cards = [cards[k] for k in range(len(cards)) if i != k != j]
                    # 尝试每种运算符
                    for op in (truediv, mul, add, sub):
                        # 避免除以零
                        if op is not truediv or num2 != 0:
                            next_num = op(num1, num2)
                            # 加入运算结果并递归
                            if self.judgePoint24(next_cards + [next_num]):
                                return True
                        # 对于减法和除法，还需要考虑反过来的情况
                        if op in (sub, truediv) and num1 != 0:
                            next_num = op(num2, num1)
                            if self.judgePoint24(next_cards + [next_num]):
                                return True
        return False

Explain

此题解采用了递归回溯的方法来解决24点游戏。主要思路是，每次递归中选择两个数字进行所有四种运算（加、减、乘、除），并将结果作为新的数字与剩余的数字一起继续递归处理，直到数组中只剩下一个数字，如果这个数字接近24（由于浮点运算，这里使用了一个小的阈值来判断），则返回true。对于除法和减法，由于它们不满足交换律，需要额外处理两个数字位置交换的情况。递归终止的基本情况是当数组中只剩一个数字，检查这个数字是否接近24。

时间复杂度: O(1) （因为输入的卡片数量固定为4，所以时间复杂度可以视为常量时间复杂度）

空间复杂度: O(4) （递归深度）

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        if len(cards) == 1:
            return abs(cards[0] - 24) < 1e-6

        # 尝试每一种分割方式
        for i in range(len(cards)):
            for j in range(len(cards)):
                if i != j:
                    # 选择两个不同的数字
                    num1, num2 = cards[i], cards[j]
                    # 剩余的数字
                    next_cards = [cards[k] for k in range(len(cards)) if i != k != j]
                    # 尝试每种运算符
                    for op in (truediv, mul, add, sub):
                        # 避免除以零
                        if op is not truediv or num2 != 0:
                            next_num = op(num1, num2)
                            # 加入运算结果并递归
                            if self.judgePoint24(next_cards + [next_num]):
                                return True
                        # 对于减法和除法，还需要考虑反过来的情况
                        if op in (sub, truediv) and num1 != 0:
                            next_num = op(num2, num1)
                            if self.judgePoint24(next_cards + [next_num]):
                                return True
        return False

Explore

递归回溯方法适用于这种问题因为24点游戏要求我们探索所有可能的数字组合和运算符组合，以找到能够形成特定值（如24）的表达式。递归允许我们深入每一种可能的运算和数字组合，而回溯则允许我们在一条路径不再有希望时放弃它，回退到上一步尝试其他可能的路径。这种方法在解决需要枚举多种组合和顺序的问题时非常高效。

在递归中处理重复数字的问题，通过在每次递归调用时创建一个新的数字列表来解决。在具体实现中，我们首先选择两个数字进行运算，然后将这两个数字从当前列表中移除，将运算结果添加到剩余数字的列表中。通过索引确保每次只选择不同的数字。这样，即使原始数组中有重复的数字，也能保证每次递归处理的是不同的数字实例，从而避免了在递归过程中多次使用同一数字的问题。

在递归过程中，终止条件是当数字列表只剩一个数字时。在每次递归中，我们通过不同的运算减少列表中的数字数量，直到列表中仅剩一个数字。如果这个数字非常接近24（由于浮点数的精度问题，通常使用一个小的阈值如1e-6来判断），我们认为找到了一个有效的解决方案，返回true。如果所有的路径都被尝试过后没有找到解决方案，最终返回false。这种方法确保了我们能够全面地探索所有可能的数字和运算符组合，直到找到答案或确认无解。