LeetCode问题：判断4个整数能否通过四则运算得到24

嘿，我最近在啃LeetCode上的24点问题——就是要写个布尔函数，给定四个整数数组，判断能不能用+、-、*、/这四则基本运算凑出24。这里得先把排列组合的逻辑理清楚，毕竟减法和除法是对顺序敏感的，和加法乘法完全不一样。

核心思路：逐步缩减数字数量 #

咱们从四个数开始，一步步把数字数量减少到1，每一步都枚举所有可能的运算组合：

1. 第一步：四个数变三个数
   因为减法、除法有顺序要求，所以不能用组合，得用排列。从4个元素中取2个的排列数是(4 P 2) = 4*3 = 12种。每种排列再搭配4种运算符，总共有12*4 = 48种可能的运算结果。每得到一个结果，就把它和剩下的两个数组成新的三个数的数组，进入下一步。
2. 第二步：三个数变两个数
   同理，从3个元素中取2个的排列数是(3 P 2) = 3*2 = 6种，搭配4种运算符，总共有6*4 = 24种可能。得到结果后和剩下的一个数组成新的两个数的数组，进入最后一步。
3. 第三步：两个数判断结果
   从2个元素中取2个的排列数是(2 P 2) = 2*1 = 2种，搭配4种运算符，总共有2*4 = 8种可能。这时候只要判断运算结果是否接近24就行——这里要注意浮点数精度问题，比如因为除法得到23.9999999999或者24.0000000001，其实都算凑出24，所以得用abs(result - 24) < 1e-6这种方式判断，不能直接用等于号。

关键细节不能忘 #

• 除法运算的时候，除数不能为0，否则会报错，所以每次做除法前必须判断除数是否接近0（同样考虑精度，比如abs(divisor) < 1e-6就跳过这个运算）。
• 递归过程中不用刻意去重，因为数字数量在逐步减少，总运算量其实不大（48248=9216种情况，完全在计算机处理范围内）。

举个实际例子 #

比如输入数组[4,1,8,7]，其中一种可行路径是：

• 先取8和4，用减法得到8-4=4，剩下的数变成[4,1,7]
• 再取7和1，用减法得到7-1=6，剩下的数变成[4,6]
• 最后用乘法得到4*6=24，符合条件，返回true

内容的提问来源于stack exchange，提问作者A is for Ambition