★ FEATURED ARTICLE 文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本篇题解来自 InterviewGuide 仓库「精选力扣 300 题目」系列之回溯算法专题。题目本身是一道经典的表达式枚举问题给定 4 张 1~9 的牌判断能否通过加、减、乘、除与括号运算得到 24。文章将以仓库中收录的直接穷举题解为主体逐行拆解其三个重载judge的递归结构并在此基础上归纳出一个更通用的回溯DFS框架同时讲清楚实数除法、浮点精度、除零剪枝等面试高频考点。读完你可以独立手写这道题并迁移到任何若干数字凑目标值的枚举型题目。题目回顾你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过*/-()的运算得到 24。示例 1输入: [4, 1, 8, 7] 输出: True 解释: (8-4) * (7-1) 24示例 2输入: [1, 2, 1, 2] 输出: False注意三条关键约束除法运算符/表示实数除法而不是整数除法。例如4 / (1 - 2/3) 12。每个运算符对两个数进行运算。特别是我们不能用-作为一元运算符。例如[1, 1, 1, 1]作为输入时表达式-1 - 1 - 1 - 1是不允许的。你不能将数字连接在一起。例如输入为[1, 2, 1, 2]时不能写成12 12。这三条注意点直接决定了算法的形态既然每个运算符都必须是二元运算那么4 个数 → 24的过程就必然可以被描述为每次取两个数、做一次运算、合并成一个数最终把一个数化简为另一个数。这也意味着括号的枚举被隐式包含在任意选两个数合并这一过程里无需显式生成括号减法与除法都存在两种方向a-b与b-a、a/b与b/a枚举时必须都覆盖由于是实数除法必须用double保存中间结果并用误差阈值EPS判断是否等于 24。思路分析问题本质是选两个数做一次二元运算假设当前还剩n个数n 2一步合法操作等价于从n个数中无序选取两个数a、b组合数C(n, 2)对a、b施加 6 种二元运算之一ab、a*b、a-b、b-a、a/b、b/a注意减法和除法各有两个方向用运算结果替换掉a、b剩余数字个数变为n-1递归继续当只剩 1 个数时判断它是否等于 24。整个过程天然构成一棵搜索树叶子节点共有C(4,2)×6 × C(3,2)×6 × C(2,2)×6 36 × 18 × 6 3888个候选结果规模是有界常数。这正是这道题可以采用穷举/回溯暴力搜索而不会超时的根本原因。解法一直接穷举仓库原版题解仓库中的原版题解采用三重judge重载的方式把上述递归过程按照参数个数 4→3→2 直接展开代码直观、无需任何辅助数据结构class Solution { public boolean judgePoint24(int[] nums) { double a nums[0]; double b nums[1]; double c nums[2]; double d nums[3]; return judge(a, b, c, d); } public boolean judge(double a, double b, double c, double d) { return // a b judge(a b, c, d) || judge(a * b, c, d) || judge(a - b, c, d) || judge(b - a, c, d) || judge(a / b, c, d) || judge(b / a, c, d) || // b c judge(c b, a, d) || judge(c * b, a, d) || judge(c - b, a, d) || judge(b - c, a, d) || judge(c / b, a, d) || judge(b / c, a, d) || // c d judge(c d, a, b) || judge(c * d, a, b) || judge(c - d, a, b) || judge(d - c, a, b) || judge(c / d, a, b) || judge(d / c, a, b) || // b d judge(b d, a, c) || judge(b * d, a, c) || judge(b - d, a, c) || judge(d - b, a, c) || judge(b / d, a, c) || judge(d / b, a, c) || // a c judge(a c, b, d) || judge(a * c, b, d) || judge(a - c, b, d) || judge(c - a, b, d) || judge(a / c, b, d) || judge(c / a, b, d) || // a d judge(a d, b, c) || judge(a * d, b, c) || judge(a - d, b, c) || judge(d - a, b, c) || judge(a / d, b, c) || judge(d / a, b, c); } public boolean judge(double a, double b, double c) { // 例如 (24, 3, 8) return judge(a b, c) || judge(a * b, c) || judge(a - b, c) || judge(b - a, c) || judge(a / b, c) || judge(b / a, c) || // judge(c b, a) || judge(c * b, a) || judge(c - b, a) || judge(b - c, a) || judge(c / b, a) || judge(b / c, a) || // judge(c a, b) || judge(c * a, b) || judge(c - a, b) || judge(a - c, b) || judge(c / a, b) || judge(a / c, b); } public boolean judge(double a, double b) { return Math.abs(a b - 24) 0.001 || Math.abs(a - b - 24) 0.001 || Math.abs(b - a - 24) 0.001 || Math.abs(a * b - 24) 0.001 || Math.abs(a / b - 24) 0.001 || Math.abs(b / a - 24) 0.001; } }逐层拆解这段代码第一层入口judgePoint24。把int[]的 4 个元素转成double后直接交给 4 参数版本的judge。转double这一步是必须的——后续所有除法都是实数除法整数除法会直接丢精度例如2/3在整数除法下等于0。第二层4 参数judge(a, b, c, d)。它枚举第一步选哪两个数合并6 组两数组合ab、bc、cd、bd、ac、ad每组对这两个数施加 6 种运算运算结果与剩下两个数一起进入 3 参数版本的judge。注意每个分组内部的两数是无序的因此a-b与b-a、a/b与b/a都要枚举共6 组 × 6 种 36个分支。第三层3 参数judge(a, b, c)。同理从 3 个数中任选两个合并3 种组合 × 6 种运算 18 个分支结果与剩下的数进入 2 参数版本。第四层2 参数judge(a, b)——递归终止条件。两个数之间同样有 6 种可能的运算结果只要任何一种与 24 的差的绝对值小于0.001就返回true。这里0.001就是浮点比较的误差阈值EPS。为什么用Math.abs(x - 24) 0.001而不是x 24这是本题最重要的工程细节之一。double无法精确表示所有十进制小数例如4 / (1 - 2/3)在计算机里会算出一个非常接近 12 但未必严格等于 12 的浮点数。如果直接用判断相等正确答案可能被浮点误差抹掉。仓库题解选用0.001作为阈值配合题目保证每个数字在 1~9 之间、运算链很短的特点足以区分真正的 24 与误差结果。面试中常见的另一种写法是Math.abs(x - 24) 1e-6原理相同只是精度等级更严。用示例验证输入[4, 1, 8, 7]取8与4做8-4 4再取7与1做7-1 6最后4 * 6 24命中 2 参数版本的终止分支返回True。输入[1, 2, 1, 2]无论括号如何组合、运算顺序如何3888 个分支全部无法凑出 24例如(12)*(12)9、(11)*(22)8等最终返回False。解法二把穷举归纳为通用的回溯DFS框架原版穷举把递归硬编码成了 4→3→2 三层重载优点是不用管理集合数据结构、代码零依赖缺点是当题目改成n 个数凑 target时就无法复用。把上面穷举的每一步抽象出来就能得到等价且可推广的回溯写法状态是当前剩余数字的列表每层任选两个数、枚举 6 种运算、合并后递归回溯时撤销合并。import java.util.ArrayList; import java.util.List; class Solution { private static final double EPS 1e-6; // 浮点误差阈值 public boolean judgePoint24(int[] nums) { ListDouble list new ArrayList(); for (int num : nums) { list.add((double) num); } return dfs(list); } private boolean dfs(ListDouble list) { // 终止条件只剩一个数判断是否等于 24 if (list.size() 1) { return Math.abs(list.get(0) - 24.0) EPS; } int n list.size(); // 任选两个不同的数无序组合避免重复搜索同一对 for (int i 0; i n; i) { for (int j i 1; j n; j) { double a list.get(i); double b list.get(j); // 构造下一层状态放入除 a、b 外的所有数 ListDouble next new ArrayList(); for (int k 0; k n; k) { if (k ! i k ! j) { next.add(list.get(k)); } } // 对 a、b 施加 6 种二元运算逐个递归失败则回溯 for (double val : ops(a, b)) { next.add(val); if (dfs(next)) { return true; } next.remove(next.size() - 1); // 撤销恢复现场 } } } return false; } // a、b 之间的 6 种合法二元运算 private ListDouble ops(double a, double b) { ListDouble res new ArrayList(); res.add(a b); res.add(a * b); res.add(a - b); res.add(b - a); if (Math.abs(b) EPS) res.add(a / b); // 除数非零才允许除法 if (Math.abs(a) EPS) res.add(b / a); return res; } }与解法一的等价性从搜索树的角度看两个版本遍历的节点集合完全一致4 个数阶段C(4,2)6种选法 × 6 种运算 36 个分支3 个数阶段C(3,2)3种选法 × 6 种运算 18 个分支2 个数阶段C(2,2)1种选法 × 6 种运算 6 个分支。DFS 版本通过构造新列表 撤销尾部元素实现了回溯的标准动作next.add(val)进入子状态子状态返回false后next.remove(next.size() - 1)把合并结果弹出从而恢复现场、尝试下一种运算。相比穷举版它的状态由ListDouble统一表示不依赖参数个数逻辑上更贴近每次任取两数合并的数学本质。剪枝除法除零与浮点比较ops中对Math.abs(b) EPS的判断是必要的剪枝当除数的绝对值接近 0 时a/b会溢出为Infinity或产生无意义结果直接跳过即可。这既避免了异常也减少了无效分支。另外注意EPS在这里同时承担了两个角色既作为两个浮点数是否相等的比较阈值也作为除数是否为零的判定阈值逻辑上是自洽的。复杂度分析时间复杂度搜索树的分支总数固定为C(4,2)×6 × C(3,2)×6 × C(2,2)×6 36 × 18 × 6 3888是一个与输入无关的常数。因此本题的暴力搜索在时间上是O(1)量级任何输入最多只需枚举 3888 条候选路径即可得出结论。空间复杂度穷举版没有额外数据结构递归深度最多 3 层空间为O(1)DFS 版每层会复制一个长度不超过 4 的列表递归深度同样最多 3 层空间仍可视为O(1)常数级别。由于状态空间极小本题不需要记忆化或哈希去重即使存在不同运算顺序得到相同中间结果集合的重复子问题其数量级也远小于 3888直接暴力即可。这与其他回溯题如组合、排列动辄指数级状态不同是本题可以放心全量枚举的原因。面试要点与易错点小结实数除法全程使用double判断4 / (1 - 2/3) 12这类中间带分数的表达式时一旦中途用了整数除法就会全盘出错。一元负号被禁止-1 - 1 - 1 - 1这种表达式不合法因此枚举时只需要两数相减的两个方向a-b与b-a不需要单目取负。禁止数字拼接[1, 2, 1, 2]不能写作12 12意味着每次运算必须严格消耗两个当前数字、产出一个新数字数字数量每次减一。浮点精度用Math.abs(result - 24) EPS判断EPS取1e-3仓库原题解或1e-6均可切忌直接比较。减/除两个方向都要枚举漏掉b-a或b/a会让(8-4)*(7-1)这类表达式无解。除零保护除法分支前先判断除数绝对值是否大于 EPS。在 InterviewGuide 仓库中的位置与延伸阅读本篇文章对应仓库路径 docs/notes/03-hunting_job/03-algorithm/03-leetcode/10-回溯算法/medium/679.24点游戏.md收录于「精选力扣 300 题目」之回溯算法专题的 Medium 难度列表。如果你希望把穷举/回溯的思路放到同一坐标系下对比仓库回溯专题还收录了这些经典题目推荐连读46. 全排列DFS 回溯的入门模板题含next_permutation与手写回溯两种解法39. 组合总和 与 40. 组合总和 II在回溯中处理选或不选与去重78. 子集 与 90. 子集 II回溯结果收集的两种时机。对比可见24 点游戏的特殊之处在于每层都要做一次二元运算并合并数字而全排列、组合、子集等题目每层只是选一个/不选一个元素。抓住状态是什么、每层做什么、何时终止这三个问题就能把不同回溯题统一到同一个思维框架下这也是校招与社招面试中考察算法题的核心评分点。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐算法通关手册 · LeetCode 0679「24 点游戏」题解回溯算法枚举四则运算组合的困难题全解析算法通关手册 · LeetCode 0679「24 点游戏」题解回溯算法枚举四则运算组合的困难题全解析 本篇基于《算法通关手册》AlgoNote中 24教程文档知识库leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱leetcode 0093 Restore IP Addresses回溯与枚举两种解法的完整实现、复杂度分析与常见陷阱 本文围绕 LeetCode 0093「示例工程教程LeetCode 17 电话号码的字母组合回溯与迭代两种解法的多语言完整剖析leetcode 仓库实战LeetCode 17 电话号码的字母组合回溯与迭代两种解法的多语言完整剖析leetcode 仓库实战 本篇文章围绕 LeetCode 第 17 题「电话示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
