LeetCode 679. 24 点游戏
题目描述
题意分析
四张牌上的数字都在
1到9之间，每张牌必须使用一次，可以调整数字顺序，选择加、减、乘、除和括号，判断能否得到24。返回是否存在合法算式，不需要输出算式本身。除法是实数除法，中间结果允许为负数或分数。不能把两张牌拼成多位数，也不能额外给某张牌添加一元负号；负数应由两个已有数相减产生。数值相同的牌仍然是不同的牌，都需要使用。
解法：回溯枚举两数合并
核心思路
[!blue]
不必分别枚举数字排列、运算符和括号，可以每次任选两项计算，再把结果放回剩余项中。开始时四项各代表一张牌；合并后的一项代表一个已经算好的子表达式。每次项数减少一，三次合并后只剩完整表达式的值。
状态中的各项始终来自互不重叠的原始牌。取出两项后用计算结果替换它们，只会合并两组牌，不会丢牌或重复用牌，因此最后一项一定使用了全部四张牌。
两两合并也能覆盖所有括号结构：任何合法表达式都可以看成二叉运算树，先计算最内层的两个子项，再逐层合并；搜索枚举任意数对和运算，就包含这棵树对应的计算顺序。只把一个累计值与剩余单张牌相算，会漏掉左右两边都先组成子表达式的情况。
对每个
i < j的数对，加法和乘法各算一次即可；减法与除法不满足交换律，必须分别尝试两个方向。除法允许产生分数，但不能除以零，因此使用浮点数，并在分母绝对值足够大时才尝试对应除法。下一状态先复制未选中的项，最后一个位置放本次计算结果。递归只读取传入状态，每次继续合并都创建更小的数组，所以兄弟分支只需重写最后一个位置，不会污染其他项。只剩一项时，用误差阈值判断它是否等于
24。
解题步骤
- 将四张牌转为浮点数，保留除法可能产生的小数部分。
- 当前只剩一项时，判断它与
24的绝对差是否小于EPS，返回结果。- 枚举所有
i < j的数对，复制未参与计算的项，建立少一项的下一状态。- 尝试加法、乘法、两个方向的减法，以及分母非零的两个方向的除法。
- 将每个运算结果写入下一状态的末尾并递归。任意分支成功即返回
true，全部组合都失败才返回false。
代码实现
class Solution {
private static final double EPS = 1e-6;
public boolean judgePoint24(int[] cards) {
double[] nums = new double[cards.length];
for (int i = 0; i < cards.length; i++) {
nums[i] = cards[i];
}
return solve(nums, nums.length);
}
private boolean solve(double[] nums, int size) {
if (size == 1) {
return Math.abs(nums[0] - 24.0) < EPS;
}
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
double[] next = new double[size - 1];
int idx = 0;
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
next[idx++] = nums[k];
}
}
// 选择两项合成一项，减法和除法都要枚举两个方向。
double a = nums[i];
double b = nums[j];
if (tryValue(next, idx, a + b)
|| tryValue(next, idx, a - b)
|| tryValue(next, idx, b - a)
|| tryValue(next, idx, a * b)) {
return true;
}
// 分母非零才尝试除法，允许中间结果为分数。
if (Math.abs(b) > EPS && tryValue(next, idx, a / b)) {
return true;
}
if (Math.abs(a) > EPS && tryValue(next, idx, b / a)) {
return true;
}
}
}
return false;
}
private boolean tryValue(double[] next, int idx, double value) {
next[idx] = value;
return solve(next, idx + 1);
}
}
import "math"
const epsilon = 1e-6
func judgePoint24(cards []int) bool {
nums := make([]float64, len(cards))
for i, card := range cards {
nums[i] = float64(card)
}
return solve24(nums)
}
func solve24(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24.0) < epsilon
}
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
next := make([]float64, len(nums)-1)
index := 0
for k := 0; k < len(nums); k++ {
if k != i && k != j {
next[index] = nums[k]
index++
}
}
a := nums[i]
b := nums[j]
// 选择两项合成一项，减法枚举两个方向，除法也分别补入。
values := []float64{
a + b,
a - b,
b - a,
a * b,
}
// 分母非零才尝试除法，允许中间结果为分数。
if math.Abs(b) > epsilon {
values = append(values, a/b)
}
if math.Abs(a) > epsilon {
values = append(values, b/a)
}
for _, value := range values {
next[index] = value
if solve24(next) {
return true
}
}
}
}
return false
}
复杂度分析
- 时间复杂度：$O(1)$，题目固定只有四张牌。每层至多为每对数尝试六种结果，叶子数量上界为 $\binom{4}{2}\times6\times\binom{3}{2}\times6\times\binom{2}{2}\times6=3888$；每个状态的复制也只处理常数项。
- 空间复杂度：$O(1)$，状态规模依次为四、三、二、一项，递归深度和同时保留的数组总量都为常数。
关键点总结
[!green]
- 每项代表一个子表达式，任选两项合并，统一覆盖运算顺序和括号结构。
- 原始牌始终被划分到互不重叠的各项中，合并自然保证每张牌恰好用一次。
- 无序数对减少重复枚举，非交换运算仍必须保留两个方向。
- 只在全部项合并后判断结果，不能因为中途出现
24就忽略剩余牌。
易错点总结
[!yellow]
- 只枚举从左向右的连续累计运算，会漏掉先分别计算两个子表达式再合并的括号结构。
- 使用整数除法，或拒绝负数和分数中间结果，会删掉合法计算路径。
- 限制
i < j后只算一个方向的减法、除法，会漏掉不同数值结果。- 用浮点数与
24直接做相等比较，可能因舍入误差错判；应比较差值与阈值。- 认为原始牌不含零就无需判分母，忽略了中间的减法可能产生零。
- 直接覆盖当前状态却不恢复，会让其他分支读取错误的剩余项；这里通过创建下一状态避免共享修改。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 241. 为运算表达式设计优先级 | 中等 | 同样枚举运算树并组合子结果，原题数字顺序和运算符固定，本题还可调整数字次序并选择四则运算。 |
| 282. 给表达式添加运算符 | 困难 | 同样搜索算式达到目标，本题允许除法与任意组合次序，原题在固定数字串间插运算符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！