24点的回溯求解算法

原题目见leetcode：

679. 24 点游戏

leetcode, 24点游戏, 回溯算法

访问网站

基本思路

1. 递归（回溯）：每一步从当前数组中选择任意两个数，计算这两个数可能得到的所有结果（+ - * /），把结果替换回数组中，继续递归。
2. 终止条件：数组长度为 1 时，用 EPS 判断该值是否等于 24。

关键实现要点

选择两个数（枚举 C(n,2)）

代码说明：用双重循环 i, j（i < j）枚举任意一对数。

for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
        // nums[i], nums[j] 是当前的数对
    }
}

解释：保证不重复且覆盖所有组合；i 从 0 到 n-2，j 从 i+1 到 n-1。

生成候选运算结果

代码说明：对选中的 a, b 生成所有可能的四则运算结果，注意除法时除数需非 0（用 EPS 判断）。

const results = [];
results.push(a + b);
results.push(a - b);
results.push(b - a);
results.push(a * b);
if (Math.abs(b) > EPS) results.push(a / b);
if (Math.abs(a) > EPS) results.push(b / a);

解释：减法和除法非交换（a-b 与 b-a 都要尝试），乘法和加法可视为交换对称但为简单起见这里保留全部结果，后续可选去重优化。

构造下一层数组并递归

代码说明：把除去 i、j 的剩余数复制到下一层数组 nextNums，再把某个候选结果 push 进去，然后递归调用。

const nextNums = [];
for (let k = 0; k < n; k++) {
    if (k !== i && k !== j) nextNums.push(nums[k]);
}

for (const res of results) {
    nextNums.push(res);
    if (solve24(nextNums)) return true; // 只要有一条分支成功就返回 true
    nextNums.pop(); // 回溯，恢复状态
}

解释：每个候选结果代表把 a 与 b 用某种运算合并为一个新数，数组长度减一，继续穷举。

终止条件与数值判断

代码说明：当数组只剩一个数时，用 EPS 判断是否为 24。

if (nums.length === 1) {
    return Math.abs(nums[0] - 24) < EPS;
}

解释：浮点计算会有误差，使用 EPS（1e-6）判断“接近等于”。

回溯与剪枝提示

说明：递归返回后需恢复 nextNums（pop），否则状态污染；可选地对 results 或（i,j）层使用 Set 去重，减少重复分支。示例剪枝：当 a === b 时，a+b 与 b+a 相同，可避免重复。

数值与精度注意点

说明：除法前判断除数绝对值大于 EPS；若要完全避免浮点误差，可用分数/有理数表示（实现复杂度上升）。

完整代码示例

下面给出完整、可运行且带注释的 JavaScript 实现：

// 完整实现：判断是否能用四则运算得到 24
const EPS = 1e-6;

function judgePoint24(cards) {
    if (!cards || cards.length === 0) return false;
    // 将所有输入转换为浮点数，避免整数除法问题
    const nums = cards.map(x => Number(x));
    return solve24(nums);
}

function solve24(nums) {
    const n = nums.length;
    if (n === 0) return false;
    if (n === 1) {
        return Math.abs(nums[0] - 24) < EPS;
    }

    // 枚举任意两个数
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            const a = nums[i];
            const b = nums[j];

            // 构造下一层数组：把除了 i, j 的数放入 nextNums
            const nextNums = [];
            for (let k = 0; k < n; k++) {
                if (k !== i && k !== j) nextNums.push(nums[k]);
            }

            // 生成所有可能的运算结果
            const results = [];
            results.push(a + b);
            results.push(a - b);
            results.push(b - a);
            results.push(a * b);
            if (Math.abs(b) > EPS) results.push(a / b);
            if (Math.abs(a) > EPS) results.push(b / a);

            // 对每个可能的结果，放回数组并递归
            for (const res of results) {
                nextNums.push(res);
                if (solve24(nextNums)) return true;
                nextNums.pop();
            }
        }
    }

    return false;
}

// 示例
console.log(judgePoint24([3, 3, 8, 8])); // true
console.log(judgePoint24([1, 1, 1, 1])); // false

如何运行

将上面代码保存为 solve24.js，然后在终端中运行：

node solve24.js

小结与后续优化建议

• 这是一道典型的回溯穷举题，关键在于如何枚举数对并正确处理浮点与除法的边界。可选优化包括：在每层对 results 去重（减少重复分支）、对对称运算（加、乘）做剪枝、或对有理数情况使用分数表示以完全避免浮点误差（复杂度和实现难度增加）。

---