4.2 24点
题目描述（第679题）
有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。
报数游戏热身过后，让我们来解决一道更贴近生活的题目。相信不少读者都玩过 24点，玩游戏的时候你是否考虑过具体算法呢？
解法一 回溯递归法
思路
4张牌加上四则运算，为拼出24点我们需要对这些数字和运算规则进行排列组合，如示例1中，输入数组为[4,1,8,7]，一种解法是将数字重新排列为8,4,7,1，同时先后进行（8-4）、（7-1）及两者的乘法。由此不难看出针对此游戏，我们是可以穷举出所有潜在结果并得到答案的，穷举的过程可以分两步进行。
● 计算4个数字的全排列，如果有重复数字应当去重。
● 针对每一种排列计算所有可能的结果，与24进行比对。
数字的排列组合
第1步需要得出给定4个数字可以产生的全部非重复排列。Python语言自带的itertools模块是实现了全排列函数的，我们可以使用它方便地得到全排列结果：[list(i)for i in itertools.permutations(nums)]。不过求排列组合实际上也是力扣（LeetCode）中的一类题目，此时的场景对应第47题全排列II问题，我们来看一看如何使用笨方法来实现全排列。
学习过排列组合的读者应该知道，n个数字的全排列一共有n!个，其推理也并不复杂：选择排列中的第1个数字时有n种选择，选择第2个数字时因为已经用掉了一个，那么还剩n– 1种选择，以此类推，直至最后一个位置的可选数字只有一个，将所有的可能性相乘就得到了最终的结果。
如果使用计算机程序实现上述过程，最适合的算法思想是什么呢？答案是回溯法，从第1位开始逐位放入数字，得到某个排列之后，如果它不是最后一个解（或者在题目的限定条件下不是正确解），回溯算法会回到上一步做一些改变，即回溯并再次尝试，直至覆盖所有可能的路径。
当存在相同数字时，全排列可能出现重复，去重可以减少不必要的计算。寻找排列前先对数字进行排序，回溯时遇到前后数字重复且前边数字已经尝试过的情况就跳过计算过程。当然去重并不是必需的，如果去重增加的额外计算成本高于带来的收益的话，也可以不进行优化。
计算排列可能的结果
有了上面的全排列结果，问题便简化成了求一组固定数字组合计算的问题。由于无法判断计算的范围，我们又需要对所有可能进行穷举。那么穷举的思路是什么呢？加/减/乘/除四则运算大家再熟悉不过了，它们的共同点在于都属于二元运算，即作用于两个变量的数学运算，因此除除数为0的特殊情况外，不管组合的先后顺序或数值如何变化，每一步始终都是两个变量的计算，无论变量是排列中的数字，还是其他数字计算得出的结果。
定义函数compute(self,nums: List[float])，判断给定数组（排列）为nums时能否凑成24点，当数组中的数字多于一个时，对于数组中所有可能的相邻数字对，两两结合计算出四则运算的结果，并使用得到的结果替换原排列中的这对数字来得到数组nums1（数组中的数字个数因此减1），重复compute(nums1)，直到只有一个数字时将它与24进行比较，得到结果。
对全排列中的每一种排列进行计算比较，我们便能得出是否可以得到24点。
其他注意事项
在大多数编程语言中，浮点数并不能完全精确地表示十进制数，并且即使是最简单的数学运算也可能引起一定的误差，比如：
因此在对计算结果进行比较时，需要考虑避免上述问题的出现，在比较24点时我们采取了下面的做法。
代码
解法二 迭代递归法
思路
在上面的穷举思路中，我们将数字排列与组合计算分成了两个部分，这样做更易于理解，但程序运行时将产生冗余。
一方面，基于加法和乘法的交换律，不同排列组合的计算过程可能是等价的，会产生重复的计算。另一方面，一旦正确解被找到，剩余的排列也就不需要再考虑了，并不需要继续穷举。
基于上述原因，我们可以考虑替换全排列的推算，将数字穷举过程与计算过程相结合。同样，基于相邻数字对组合计算的方法，我们直接在原数组的基础上进行尝试即可。
定义函数compute(self,nums: List[int],n: int)，其中n表示当前数组中的变量个数。使用数组下标left、right指向数字对，针对每一种排列（既包含初始的4个数字的排列，也包含使用计算结果产生的新数字排列），由左向右进行两两组合并计算四则运算的结果。与上一解法的不同之处在于：两数字并不需要相邻，因为数组的排列并未固定；计算时两数字的前后顺序并不固定，这意味着减法和除法将产生两种结果。使用与上题类似的递归法，可以穷举得到最终的结果。
代码
