这题其实就类似于算24点,做法很多,这里提供一种几乎不用动脑子的做法(?
首先我们将4个数形成一个列表,比如样例的 (1,2,3,4)(1,2,3,4)(1,2,3,4)。接着我们枚举任意两个数,对这两个数进行加/减/乘/除/反向加/反向减的操作,并将操作后的数放在两个数的任意一个,另外一个数置为 −1-1−1 表示此位置已经没有数。比如我们选的这两个数是 1,31,31,3,那么进行这六种操作后分别为 1+3,1−3,1×3,1/3,3−1,3/11+3,1-3,1\times 3,1/3,3-1,3/11+3,1−3,1×3,1/3,3−1,3/1,若我们选择 1+3(=4)1+3(=4)1+3(=4),则操作后的列表为
(4,2,−1,4)(4,2,-1,4)(4,2,−1,4)。接着递归处理(即回溯dfs)这个数列,直到列表中只剩下一个数时,我们检查这个数是否是 242424 的倍数即可。
那么假如我们发现最后的数满足条件,如何根据此生成一个符合的表达式呢?我们只需记录每一步操作的两个数的位置编号以及操作编号 (1,2,3,4,5,61,2,3,4,5,61,2,3,4,5,6 分别代表 加/减/乘/除/反向减/反向除),接着倒序递归输出即可。如果当前的这个编号的数是原序列中的(即之前没有操作过这个编号的数),那么直接输出之即可。否则需要递归到上一次处理的位置重复这个操作。比如,拿 (1,2,3,4)(1,2,3,4)(1,2,3,4) 来说,假设我们记录的位置编号及操作编号分别为:
操作数1 操作数2 操作编号 111 111 222 1(+)1(+)1(+) 222 333 444 3(×)3(\times)3(×) 333 111 333 3(×)3(\times)3(×)
那么我们先考虑最后一行。发现第一个操作数 111 不是原始序列的数,因为第一行操作又用到了 111,所以先加个左括号,之后递归考虑第一行,发现第一行使用的编号 111 的数确实是原始序列的,编号 222 的数也是。因此直接输出原始数 1+21+21+2 即可。此处递归结束后接着加入右括号,即变成 (1+2)(1+2)(1+2)。
第一个数考虑完后在中间加入运算符号 ×\times×。同理继续考虑第二个操作数 333,发现他也在第二行出现过,不是原始数。于是递归考虑第二行,得 (3×4)(3 \times 4)(3×4)。
于是最终结果 (1+2)×(3×4)(1+2) \times (3 \times 4)(1+2)×(3×4),这个不是 242424 的倍数,只是为了展示递归输出的机理。