每日算法 — 使用java实现24点游戏：子集划分与位掩码状态压缩DP

24 点游戏规则一句话：给你四张牌，用加减乘除和括号，让结果等于 24。每张牌必须用且只能用一次。

看起来是个”枚举所有表达式”的暴力题，但一旦你认真写起来，很快就会撞到两个坑：

表达式结构怎么枚举？四张牌的全排列是 4!=24 种，三个运算符位置是 4³=64 种，五套括号结构……组合起来数量不小，而且括号结构必须显式枚举，否则会漏解。
浮点数误差。经典题目 3 3 8 8 的唯一解是 8 / (3 - 8/3)，中间会出现 8/3 这种无限小数。用 double 判等，24.000000000000004 != 24，程序会误判为无解。

本文给出一个绕开这两个坑的建模方式：把”选牌”变成位掩码（bitmask），把”合并两组牌”变成子集划分，用状态压缩 DP 一次性算出所有可达值，并且全程使用精确分数运算。

一、核心建模：dp[mask] 能算出什么

设四张牌编号 0~3。用 4 位二进制 mask 表示”用了哪些牌”：

mask = 0001 表示只用了第 0 张牌
mask = 1111 (十进制 15) 表示四张全用，这是我们要的终态
mask = 0000 表示一张没用

定义 dp[mask] = 仅使用 mask 中这些牌，能算出的所有数值的集合。

状态转移的本质就是一次子集划分：

dp[mask] = ∪ over 所有划分 (A, B), A ∪ B = mask, A ∩ B = ∅
             { a op b | a ∈ dp[A], b ∈ dp[B], op ∈ {+, -, *, /} }

也就是说，任何一个由 mask 中牌组成的表达式，其最外层运算符必然把牌分成左右两组。反过来，只要枚举所有分组方式，再把两组的所有可能值两两组合，就能得到 mask 的全部可能值。

以 mask = 1111（四张牌）为例，它的划分方式：

{0}   ∪ {1,2,3}
{1}   ∪ {0,2,3}
{2}   ∪ {0,1,3}
{3}   ∪ {0,1,2}
{0,1} ∪ {2,3}
{0,2} ∪ {1,3}
{0,3} ∪ {1,2}

共 7 种（不计左右顺序）

为什么这个建模比”枚举表达式”更好？

不会漏括号：每一种括号结构都对应唯一一种划分（二叉表达式树的左右子树就是划分的两部分），全部被枚举到。
不会重复：同一组牌的不同排列被 mask 天然合并，dp 里用 Map 去重，重复值只保留一份。
可扩展：牌数变成 5、6 张时，只需扩大 mask 范围，算法结构不变（虽然会变慢）。

二、精确分数：彻底消灭浮点误差

判定”是否等于 24″必须是精确比较。这里用一个不可变的分数类，分子分母都是 long，构造时立刻约分：

/** 精确分数：num/den，den 恒为正，且约分到最简 */
static final class Frac implements Comparable<Frac> {
    final long num, den;

    Frac(long n, long d) {
        if (d < 0) { n = -n; d = -d; }                  // 保证分母为正
        long g = gcd(Math.abs(n), d);
        if (g == 0) g = 1;                              // 处理 0/0 之外的退化情况
        this.num = n / g;
        this.den = d / g;
    }

    Frac(long v) { this(v, 1); }

    static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }

    Frac add(Frac o) { return new Frac(num * o.den + o.num * den, den * o.den); }
    Frac sub(Frac o) { return new Frac(num * o.den - o.num * den, den * o.den); }
    Frac mul(Frac o) { return new Frac(num * o.num, den * o.den); }

    Frac div(Frac o) {
        if (o.num == 0) return null;                    // 除零非法，返回 null 表示该运算无效
        return new Frac(num * o.den, den * o.num);
    }

    @Override public boolean equals(Object o) {
        return o instanceof Frac && ((Frac) o).num == num && ((Frac) o).den == den;
    }
    @Override public int hashCode() { return (int) (num * 31 + den); }
    @Override public int compareTo(Frac o) { return Long.compare(num * o.den, o.num * den); }

    @Override public String toString() {
        if (den == 1) return String.valueOf(num);
        return num + "/" + den;
    }
}

三个设计要点：

约分在构造时完成。这样 1/2 和 2/4 在 equals、hashCode 上自动等价，直接放进 HashMap 就能去重，不需要额外维护规范形式。

除零返回 null。用 null 表示”这个运算不合法”，比抛异常更轻量，也比返回一个特殊值（如 NaN）更安全——因为特殊值可能在后续运算中被”洗白”成合法值。

hashCode 与 equals 必须一致。因为构造时已约分，num 和 den 的组合唯一确定一个分数，所以 num*31+den 是合法哈希，不会出现”等价但哈希不同”的情况。

关于 long 的溢出边界：四张牌最大是 13，最坏情况的分子分母增长是有限制的。四张牌的连乘最多 13⁴ = 28561，加上减法/除法产生的分数，分子分母实际不会超过 10⁶ 量级，long 绰绰有余。但如果是 6~8 张牌，就必须检查溢出了。

三、子集枚举技巧：m = (m-1) & mask

枚举 mask 的所有真子集，最朴素的做法是 for (a = 1; a < mask; a++) if ((a & mask) == a)——每轮检查 2^n 次，浪费大量时间。

标准技巧是直接”在 mask 的子集空间里递减”：

// 从 mask 的最大真子集开始，每次跳到下一个更小的子集
for (int a = (mask - 1) & mask; a > 0; a = (a - 1) & mask) {
    int b = mask ^ a;
    // 此时 A = a, B = b, 且 A ∪ B = mask, A ∩ B = ∅
}

(a - 1) & mask 的含义是：从 a 减去 1（把最低的 1 变 0、低位全变 1），然后与 mask 相与，把不属于 mask 的位清掉。这样得到的正好是”比 a 小的最大 mask 子集”。整个循环恰好遍历所有真子集，共 2^popcount(mask) – 2 次。

不过还有一个更重要的去重技巧：同一个划分 (A, B) 会被枚举两次（一次 A 在前，一次 B 在前）。如果对每次划分都做 A op B 和 B op A，就会有大量重复计算。

解决办法是固定最低位的归属：

int lowBit = mask & -mask;          // mask 的最低位（提取最低的 1）
for (int a = (mask - 1) & mask; a > 0; a = (a - 1) & mask) {
    if ((a & lowBit) == 0) continue;   // 要求 A 必须包含最低位 -> 每种划分只枚举一次
    int b = mask ^ a;
    if (b == 0) continue;
    combine(a, b, mask);
}

lowBit 是 mask 中最低的那个 1。要求 A 包含它、B 不包含它，就唯一确定了 A/B 的身份——每个无序划分只会出现一次。这把划分枚举量精确减半。

四、合并两组值：六种运算

拿到划分 (A, B) 后，把双方所有值两两组合。注意减法与除法都有两个方向：

/** 把两个子集的所有值两两组合，写入目标 mask */
static void combine(int maskA, int maskB, int target) {
    Map<Frac, Expr> A = dp[maskA], B = dp[maskB];
    for (Map.Entry<Frac, Expr> ea : A.entrySet()) {
        for (Map.Entry<Frac, Expr> eb : B.entrySet()) {
            Frac x = ea.getKey(), y = eb.getKey();
            String sx = ea.getValue().text, sy = eb.getValue().text;

            put(target, x.add(y), "(" + sx + " + " + sy + ")");           // a + b
            put(target, x.sub(y), "(" + sx + " - " + sy + ")");           // a - b
            put(target, y.sub(x), "(" + sy + " - " + sx + ")");           // b - a（方向不同，结果不同）
            put(target, x.mul(y), "(" + sx + " * " + sy + ")");           // a * b

            Frac d1 = x.div(y);
            if (d1 != null) put(target, d1, "(" + sx + " / " + sy + ")");  // a / b
            Frac d2 = y.div(x);
            if (d2 != null) put(target, d2, "(" + sy + " / " + sx + ")");  // b / a
        }
    }
}

为什么不是四种而是六种？因为减法和除法不满足交换律：3 - 8 = -5，但 8 - 3 = 5；8 / 3 和 3 / 8 完全不同。加法和乘法只需一次，减法和除法各需两次。所以是 2 + 2 + 1 + 1 = 6 种。

put 负责去重与剪枝：

/** 写入一个可达值；已存在则跳过，量级过大则剪枝 */
static void put(int mask, Frac v, String text) {
    if (dp[mask].containsKey(v)) return;                    // 该值已记录，跳过
    // 剪枝：中间值过大或分母过大时丢弃——它们无法在剩余步骤里回到 24 附近
    if (Math.abs(v.num) > 100_000 || v.den > 100_000) return;
    dp[mask].put(v, new Expr(v, text));
}

剪枝条件 |num| > 100000 是一个经验阈值。它的依据是：四张牌最大 13，后续还能做的运算次数有限，一个中间值如果已经超过 10 万，即使乘以最大值或除以最小值，也很难在剩余步数内精确落回 24。而分母超过 10 万同理——这种”丑陋分数”在剩余步骤里几乎不可能被消成整数 24。对于 n=4 这个剪枝几乎不触发（状态数只有几百），但它是 n≥5 时控制状态爆炸的关键。

五、主循环与完整代码

/** dp[mask]：该集合能算出的所有值（用 Map 去重，同一值只保留一个表达式） */
static Map<Frac, Expr>[] dp;
static int n;

@SuppressWarnings("unchecked")
static void solve(int[] cards) {
    n = cards.length;
    int full = 1 << n;
    dp = new Map[full];
    for (int i = 0; i < full; i++) dp[i] = new HashMap<>();

    // 边界：单张牌，dp 里只有它自己的值
    for (int i = 0; i < n; i++) {
        Frac v = new Frac(cards[i]);
        dp[1 << i].put(v, new Expr(v, String.valueOf(cards[i])));
    }

    // 按 mask 数值从小到大递推：子集一定小于自身，保证子集先算完
    for (int mask = 1; mask < full; mask++) {
        if (Integer.bitCount(mask) < 2) continue;          // 单元素无需转移
        int lowBit = mask & -mask;
        for (int a = (mask - 1) & mask; a > 0; a = (a - 1) & mask) {
            if ((a & lowBit) == 0) continue;               // 保证每种划分只枚举一次
            int b = mask ^ a;
            if (b == 0) continue;
            combine(a, b, mask);
        }
    }
}

为什么”按 mask 数值从小到大”就能保证子集先算完？ 因为任何真子集 A ⊂ mask 都有 A < mask（去掉至少一位 1，数值必然更小）。所以顺序递推即可，不需要拓扑排序或递归。

完整项目结构：

game24/
├── Game24DP.java        // 单文件：分数类 + 位掩码 DP + 表达式重建
└── README.md

表达式重建靠 Expr 里保存的字符串：

/** 一个可达值 + 它的表达式字符串 */
static final class Expr {
    final Frac val;
    final String text;
    Expr(Frac v, String t) { val = v; text = t; }
}

每次 put 时把左右子表达式拼成 (左 op 右)，这样终态 dp[1111] 里查 24 就能直接拿到完整表达式。代价是字符串拼接会占一些内存——如果只要”是否可解”的布尔答案，可以把 text 去掉，性能还能再提升 30% 左右。

六、运行结果

用五组代表性题目实测（含两道最容易判错的经典题）：

牌 [3, 3, 8, 8] -> (8 / (3 - (8 / 3))) = 24（dp 状态 451 个，耗时 51164 µs）
牌 [1, 5, 5, 5] -> ((5 - (1 / 5)) * 5) = 24（dp 状态 249 个，耗时 1402 µs）
牌 [4, 1, 8, 7] -> (((4 * 8) - 7) - 1) = 24（dp 状态 762 个，耗时 1567 µs）
牌 [1, 2, 3, 4] -> (2 / ((1 / 4) / 3)) = 24（dp 状态 414 个，耗时 786 µs）
牌 [3, 3, 7, 7] -> (((3 / 7) + 3) * 7) = 24（dp 状态 441 个，耗时 2511 µs）

几个值得注意的点：

3 3 8 8 与 3 3 7 7 都解出来了，且都走了”先造一个丑分数再消掉”的路子——8/(3-8/3) 和 (3+3/7)*7。这正是浮点实现最容易失败的题：8/3 = 2.6666666666666665，3 - 2.6666666666666665 = 0.33333333333333348，8 / 0.33333333333333348 = 23.99999999999999。用 double 判 == 24 直接失败。

第一个案例耗时 51ms，其余都在 1~2.5ms。原因是 3 3 8 8 有两张相同的牌，dp[0011]（两张 3）的各种组合会产生大量分母很大的分数，导致后续 Map 操作规模膨胀——同时这是进程首次运行，包含 JIT 预热成本。多次运行后稳定在 3~5ms。

1 2 3 4 的解 2 / ((1/4)/3) 看起来很怪，但它确实是合法解：1/4 = 0.25，0.25/3 = 1/12，2/(1/12) = 24。DP 不追求”好看的解”，只求”存在的解”——这也说明为什么它比”人工枚举常见表达式模板”的写法更可靠。

七、复杂度分析

指标	复杂度	n=4 时的实际值
mask 总数	O(2^n)	16
划分枚举总数	O(3^n)	3⁴ = 81
每个划分的合并	O(\|dp[A]\| × \|dp[B]\| × 6)	通常几十到几百
总体时间	O(3^n × 平均状态数)	1~5 ms

3^n 的来源很清晰：mask 中的每个元素有三种归属——在 A、在 B、不在 mask。所以所有 mask 的所有划分总和恰好是 3^n。这个数字说明：n 从 4 增到 5，理论量涨 3 倍；增到 6 涨 9 倍。实际上 n=6 时状态数膨胀远不止 9 倍（因为 dp 集合本身也在变大），需要配合更激进的剪枝（比如限制分母大小、只保留接近 24 的量级）才跑得动。

三条延伸方向的思路：

判定而非求解：如果只想知道”这四张牌有没有解”，把 Expr 去掉、dp[mask] 换成 HashSet<Frac> 即可，速度快 30%，内存降一半。
枚举全部解：把 put 改成”值 -> 表达式列表”，并对语义等价的表达式（如 a+b 与 b+a）做规范化，就能列出所有本质不同的解。
推广到”任意目标值”：把 dp[full].get(new Frac(24)) 换成查任意目标 T，同一套 DP 可以回答”这四张牌能凑出哪些整数”这个更有趣的问题——实际上本文的 dp 已经包含了全部可达值，只是我们只查了 24。

24 点游戏最值得学习的地方，是它展示了建模选择如何决定实现质量。同样是”穷举所有表达式”，按排列组合枚举要处理括号、优先级、浮点误差三大麻烦；而按”子集划分 + 位掩码”建模，这三件事一个都不存在——位掩码天然处理了”用哪些牌”，子集划分天然处理了”括号结构”，分数类天然处理了精度。选对了表示，算法难度会掉一个数量级。

Tagged with: 24点游戏 DFS 位掩码子集划分状态压缩DP 精确分数运算