LeetCode 679. 24 点游戏
目录
题目描述
题意分析
给定恰好 4 张牌，每张牌的点数在 1 到 9 之间。要判断能否用加、减、乘、除四种运算和任意括号，把这 4 个数每个恰好用一次地组合起来，使结果等于 24，返回布尔值即可，不需要输出算式。
有几个约束信号必须读准。第一，除法是实数除法而不是整除，题面明确举了
4 / (1 - 2/3) = 12这类例子，所以中间结果会出现分数，不能用整数运算糊弄过去。第二，数字不能拼接，1和2不能凑成12。第三，牌数固定是 4，不是变长输入，这说明搜索空间是常数，可以放心暴力。边界上要注意：输入点数虽然都不为 0，但中间结果可能为 0（比如
3 - 3），所以做除法前必须检查除数；括号可以任意加，意味着运算顺序完全自由，不能只按从左到右结合来枚举；由于实数除法引入无限小数，最终判定必须容忍误差。
解法：回溯枚举两数合并
核心思路
直接枚举数字排列、运算符和括号容易漏掉分组方式。更自然的做法是把表达式看成二叉树：每次从当前集合中任选两个值做一次运算，再用运算结果替换它们。集合大小从 4 依次降到 1，合并顺序就对应括号顺序。
状态定义：状态是当前的数字多重集合。每个值都代表一个已经计算完成的子表达式，并且这些子表达式使用的原始牌互不重叠。因此，取出两个值再放回一个结果，天然保证每张牌恰好使用一次。
对下标
i < j的一对数a、b，枚举：a + b、a * b、a - b、b - a、a / b、b / a。加法、乘法满足交换律，各算一次即可；减法、除法必须保留两个方向，除法还要跳过接近 0 的分母。搜索完备性：任何合法的全括号表达式都是一棵二叉树。任选一个最底层内部结点，它的两个孩子已经是可计算的值；先合并这两个孩子，再对缩小后的树重复该过程，最终一定能得到一条两两合并序列。回溯枚举了每一步的数对、运算和非交换运算方向，所以包含这条序列。反过来，每条搜索分支都只合并两个不相交的子表达式，因此生成的也一定是合法表达式。由此搜索既不漏解，也不会使用额外的牌。
当只剩一个值时，用
|value - 24| < 1e-6判断。除法会产生无法精确表示的浮点数，例如[3,3,8,8]的解依赖8 / (3 - 8/3)，不能直接使用== 24。
解题步骤
- 把 4 个整数转成浮点数，避免除法变成整数除法。
- 若集合只剩一个值，判断它与 24 的差是否小于误差阈值。
- 枚举所有
i < j的数对，并复制其余数字到下一状态。- 枚举这一对数的加、乘、双向减、双向除；分母接近 0 时跳过对应除法。
- 把结果放入下一状态并递归；任一分支成功就立即返回
true，全部失败才返回false。例如
[4,1,8,7]的一条成功路径是{4,1,8,7} → {1,7,4} → {4,6} → {24}，对应先算8 - 4、再算7 - 1，最后相乘。这个例子也说明两两合并能够表达(a op b) op (c op d)这样的左右分组。
代码实现
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)$。牌数固定为 4，搜索叶子上界为 $\binom{4}{2} \times 6 \times \binom{3}{2} \times 6 \times \binom{2}{2} \times 6 = 3888$；若推广到任意牌数则是指数级搜索。
- 空间复杂度：$O(1)$。递归深度最多 3，每层状态数组长度不超过 3。
关键点总结
- 用「任选两数合并」代替显式枚举括号，搜索状态更统一，也容易证明完备。
i < j去掉数对顺序的重复；加、乘只算一次，但减、除必须算两个方向。- 状态不变量保证每个中间值来自互不重叠的牌，因此每张牌恰好使用一次。
- 结果判等和分母判零都使用同一个误差量级。
- 输入固定为 4，先保证搜索完整；记忆化和复杂去重都没有必要。
易错点总结
- 只枚举左结合形式：
[4,1,8,7]需要覆盖(8 - 4) * (7 - 1)这类左右分组。- 使用整数除法：
[3,3,8,8]的解需要中间结果8/3，整数除法会直接丢失这条路径。- 遗漏反向减法或除法：限定
i < j后，必须显式加入b - a、b / a，否则会漏解。- 直接使用
== 24：浮点误差可能得到23.99999999999999，应使用误差比较。- 未检查分母：原始牌非 0，但
a - b可能产生 0；除法前仍要判零。- 就地覆盖状态却不恢复：兄弟分支会读到上一分支的中间值；复制下一状态可以直接避免污染。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 241. 为运算表达式设计优先级 | 中等 | 同样穷举括号方案，但按运算符位置分治并返回全部结果而非判定 |
| 46. 全排列 | 中等 | 回溯枚举的是元素顺序，用访问标记而非集合合并 |
| 473. 火柴拼正方形 | 中等 | 回溯把元素分配进固定容量的四组，靠排序与剪枝控制搜索规模 |
| 698. 划分为k个相等的子集 | 中等 | 分组数 k 是变量，需要记忆化或位掩码压缩状态 |
| 51. N 皇后 | 困难 | 逐行放置并维护列与对角线冲突集合，回溯时要显式撤销标记 |