94. 24 点游戏.md

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。*

#回溯
class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        TARGET = 24
        EPSILON = 1e-6
        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
        #构造递归
        def solve(nums: List[float]) -> bool:
            #递归终止条件
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPSILON
            #各种情况
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i != j:
                        newNums = list()
                        for k, z in enumerate(nums):
                            if k != i and k != j:
                                newNums.append(z)
                        for k in range(4):
                            if k == ADD:
                                newNums.append(x + y)
                            elif k == MULTIPLY:
                                newNums.append(x * y)
                            elif k == SUBTRACT:
                                newNums.append(x - y)
                            elif k == DIVIDE:
                                if abs(y) < EPSILON:
                                    continue
                                newNums.append(x / y)
                            if solve(newNums):
                                return True
                            newNums.pop()
        #调用递归
        flag = solve(nums)
        if flag == True:
            return True
        return False

#递归
class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        #递归终止条件
        if len(nums)==1:
            return abs(24-nums[0])<=10**(-10)
        # 每次把计算结果 和之前nums数组中其他元素组成的列表concate起来 作为新的nums 向下递归
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if self.judgePoint24([nums[i]+nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): 
                    return True
                if self.judgePoint24([nums[i]*nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): 
                    return True
                if self.judgePoint24([nums[i]-nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): 
                    return True
                if self.judgePoint24([nums[j]-nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]): 
                    return True
                if nums[j]!=0 and self.judgePoint24([nums[i]/nums[j]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):
                    return True
                if nums[i]!=0 and self.judgePoint24([nums[j]/nums[i]]+nums[0:i]+nums[i+1:j]+nums[j+1:]):
                    return True
        # 走到这一步 说明之前都不行
        return False