leetcode问题

Question

老师，leetcode的679. 24 点游戏，这道题我知道先去求个全排列，但是全排列之后，怎么使用递归穷举对所有全排列计算所有可能的式子的值呢?这道问题我冥思苦想了好久- -，老师能给一个大致的思路吗?

Answer 1

liuyubobobo 2020-03-01 18:39:02

如果已经确定 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 函数。

继续加油！：）

• 提问者 Sunny_SunshineX #1

  老师能不能进一步解释一下为什么运算顺序只有这三种？

• liuyubobobo 回复 提问者 Sunny_SunshineX #2

  穷举出来的。。。 你再找找第四种试试看？

• 提问者 Sunny_SunshineX 回复 liuyubobobo #3

  "a op1 b op2 c op3 d",  "a op1 (b op2 c) op3 d", "(a op1 b) op2 c op3 d", "a op1 b op2 (c op3 d)",  "a op1 (b op2 c op3 d)",  "(a op1 b op2 c) op3 d"，"(a op1 (b op2 c)) op3 d"，"a op1 ((b op2 c) op3 d)"。老师那以上这么多种是不是已经包含在你的那三种运算顺序里面了呢，如果是，可以麻烦解释一下为什么吗?

点开查看后面1条评论