01 问题描述

你有 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 。

02 暴力解法1-思想

24点游戏是一个耳熟能详的游戏，对于给定的4个数和4个操作符，我首先想到的方法就是暴力穷举。
具体来说，首先从给定的4个数里有序地选2个（为什么要有序呢，因为2-4和4-2的结果是完全不同的），一共有4×3=12个选择，然后4个操作符随机选一个，得到的结果和剩下的2个数字一起进入下一轮。
下一轮中，3个数里依旧有序地选择2个，一共3×2=6个选择，然后依旧4个操作符随机选一个，得到的结果和最后1个数字进入下一轮选择。
最后一轮，只剩2个数字，有序排列，有2种可能，然后选择操作符。
综上，一共有4×3×4×3×2×4×2×4=9216种可能。验证这些可能的计算结果是否等于24，如果有的话就直接返回return True。

具体实现过程中，使用一个新的list来存储当前剩余的数字。
另外，为了进行实数的除法，这里使用python中的Fraction模块

03 暴力解法2-code

这里代码部分参考了官方提供的解法

#python3
from  fractions import Fraction #python中进行分数计算
class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if not nums or len(nums)!=4:
            return False

        def run(nums:List[float]) -> bool:
            if not nums:
                return False
            if len(nums)==1:
                return abs(nums[0]-24) == 0 
            for i,x in enumerate(nums):
                for j,y in enumerate(nums):
                    if(i == j):
                        continue
                    newNums = []
                    for k,z in enumerate(nums):
                        if k != i and k != j:
                            newNums.append(z)
                    for k in range(4):
                        if k == 0:
                            newNums.append(x+y)
                        elif k ==1 :
                            newNums.append(x-y)
                        elif k==2 :
                            newNums.append(x*y)
                        elif k ==3 :
                            if y == 0:
                                continue
                            newNums.append(Fraction(x,y))
                        if run(newNums):
                            return True
                        newNums.pop()
            return False

        return run(nums)

04 暴力解法2-思想

python3里面有一个itertools模块，可以帮助我们遍历一个序列中元素的所有可能的排列或组合。如果我们想要用上这个module，应该怎么样进行穷举呢？
穷举的思想变成了：
首先对于给定的4个数进行有序排列，一共有4×3×2×1=24种组合，这部分的工作可以用itertools模块实现。
然后对于给定的4个有序的数字，例如，[a,b,c,d]，我们需要为他们选择3个运算符，共有4^3= 64种组合。
最后对于已经指定了彼此之间运算符的4个有序数字，例如，a obs1 b obs c obs d，我们需要选择运算符计算的顺序，对于3个有序的运算符，一共有3×2=6种可能。这步操作相当于为表达式增加了括号。
因此，一共的可能性就是 24 × 64 × 6 = 9216种，和第二章节得到的结果一模一样。

05 暴力解法2-code

#python3
from fractions import Fraction #python中进行分数计算
from itertools import permutations #得到序列中所有元素的所有可能排列组成
from itertools import product

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if not nums or len(nums)!=4:
            return False

        def compute(nums:List[float]) -> float :
            op = nums[1]
            a = nums[0]
            b = nums[2]
            if op== 0:
                return a+b
            elif op == 1 :
                return a-b
            elif op == 2:
                return a*b
            elif op == 3 and b!=0 :
                return Fraction(a,b)
            elif b==0 :
                return -1000000 #当除数是0的时候，也必须返回一个值，不然会报错无法进行后续计算


        x = list(range(4))

        for permu in permutations(nums):
            for op in product(x,x,x):
                newList = list(permu) + []
                for i in range(3):
                    newList.insert(i*2+1,op[i])
                
                #手动遍历6种计算组合，有2种结果一样，被我注释掉了
                if compute([compute(([compute(newList[0:3])]+newList[3:5]))]+newList[5:])==24: return True
                elif compute([compute(newList[0:3])]+newList[3:4]+[compute(newList[4:])]) == 24: return True
                elif compute([compute(newList[:2]+[compute(newList[2:5])])]+newList[5:]) ==24: return True
                elif compute(newList[:2]+[compute([compute(newList[2:5])]+newList[5:])]) ==24: return True
                #elif compute([compute(newList[:3])]+newList[3:4]+[compute(newList[4:])]) ==24 : return True
                elif compute(newList[:2]+[compute(newList[2:4]+[compute(newList[4:])])])==24 : return True
        
        return False