1回答

liuyubobobo

2020-03-01

如果已经确定 4 个数字 a, b, c, d 的一个顺序以后，下面要做的，就是在这 4 个数字之间添加运算符，假设叫 op1, op2, op3。op1, op2, op3 也应该穷举。

每决定一组 op1, op2, op3，对于 a op1 b op2 c op3 d 这个式子，运算顺序有五种，推导过程如下：

如果先计算 op1 的话，剩下的计算，或者先计算 op2, 或者先计算 op3，得到如下两种：

1. ((a op1 b) op2 c) op3 d 

2. (a op1 b) op2 (c op3 d)

如果先计算 op2 的话，剩下的计算，或者先计算 op1, 或者先计算 op3，得到如下两种：

3. (a op1 (b op2 c)) op3 d

4. a op1 ((b op2 c) op3 d)

如果先计算 op3 的话，剩下的计算，或者先计算 op1, 或者先计算 op2，得到如下两种：

5. (a op1 b) op2 (c op3 d)，这个和 2. 一样

6. a op1 (b op2 (c op3 d))

综上一共 5 种运算，穷举即可。

我的参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0679-24-Game/cpp-0679/main.cpp

犯懒，全排列没有自己写递归，直接使用 C++ 的 next_permutation 了。不过你这个问题的核心，应该是我的代码中的 ok 函数。

继续加油！：）

1

4

liuyubobobo

回复

Sunny_SunshineX

我又想了一下，一共应该是 5 种，题目的测试用例应该不全，我三种也 ac 了。我把这 5 种的推导方式补充在原答案中了。其实就是 op1 op2 op3 三个运算符的运算顺序，全排列共 6 种，其中两种是重复的。继续加油！：）

2020-03-03

共4条回复