题解 | #24点游戏算法#
24点游戏算法
http://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
方法一：回溯
一共有 44 个数和 33 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 44 个数字中有序地选出 22 个数字，共有4×3=12 种选法，并选择加、减、乘、除 44 种运算操作之一，用得到的结果取代选出的 22 个数字，剩下 33 个数字。
然后在剩下的 33 个数字中有序地选出 22 个数字，共有 3×2=6 种选法，并选择 44 种运算操作之一，用得到的结果取代选出的 22 个数字，剩下 22 个数字。
最后剩下 22 个数字，有 22 种不同的顺序，并选择 44 种运算操作之一。
因此，一共有12×4×6×4×2×4=9216 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 22 个数字，再选择一种运算操作，用计算得到的结果取代选出的 22 个数字，这样列表中的数字就减少了 11 个。重复上述步骤，直到列表中只剩下 11 个数字，这个数字就是一种可能性的结果，如果结果等于 2424，则说明可以通过运算得到 2424。如果所有的可能性的结果都不等于 2424，则说明无法通过运算得到 2424。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
进行除法运算时，除数不能为 00，如果遇到除数为 00 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 00 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 00。
还有一个可以优化的点。
加法和乘法都满***换律，因此如果选择的运算操作是加法或乘法，则对于选出的 22 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
一共有 44 个数和 33 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 44 个数字中有序地选出 22 个数字，共有4×3=12 种选法，并选择加、减、乘、除 44 种运算操作之一，用得到的结果取代选出的 22 个数字，剩下 33 个数字。
然后在剩下的 33 个数字中有序地选出 22 个数字，共有 3×2=6 种选法，并选择 44 种运算操作之一，用得到的结果取代选出的 22 个数字，剩下 22 个数字。
最后剩下 22 个数字，有 22 种不同的顺序，并选择 44 种运算操作之一。
因此，一共有12×4×6×4×2×4=9216 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 22 个数字，再选择一种运算操作，用计算得到的结果取代选出的 22 个数字，这样列表中的数字就减少了 11 个。重复上述步骤，直到列表中只剩下 11 个数字，这个数字就是一种可能性的结果，如果结果等于 2424，则说明可以通过运算得到 2424。如果所有的可能性的结果都不等于 2424，则说明无法通过运算得到 2424。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
进行除法运算时，除数不能为 00，如果遇到除数为 00 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 00 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 00。
还有一个可以优化的点。
加法和乘法都满***换律，因此如果选择的运算操作是加法或乘法，则对于选出的 22 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。