题目重点：每次合并一对数，覆盖所有表达式树，保留减除两个方向并用Fraction避免浮点判等。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练恰好四个整数，每个使用一次，允许+、−、×、÷及任意括号，不允许拼接或额外常数。
- 中间结果可为负数和有理数；不允许除以0，目标精确等于24。
- 只返回能否实现；展示输入可含0/负数，标准1–9牌面是其子集。
解题路线
- 一个表达式是二叉运算树，任一非叶节点把两个子表达式结果合成一个。逆向看可以反复从当前数池取两项合并，最终剩一项；穷举所有两项与运算覆盖全部括号结构。
- 对一对a,b，加法和乘法只需各一种结果，减法保留a−b与b−a，除法保留a/b和b/a并分别检查分母。只用一个顺序会漏掉有效表达式。
- 每次移除选中两项，加入结果，递归数池长度减1；数字重复也仍代表不同已使用实例，按位置移除不能按值一次删除全部相等元素。
- 用Fraction精确表示有理数，例如8/(3−8/3)=24。浮点近似可以设epsilon，但要证明误差或接受边界；四数题用精确分数更直接，不能四舍五入中间值。
- 相同有理结果去重，失败数池按排序后的Fraction元组记忆。只求存在性时未来可做的运算只取决于当前数值多重集，不取决于生成历史；若要输出所有表达式，历史信息不能这样全部合并。
- 不按“大于24就剪枝”或“非整数就丢弃”，减法、除法可以把大数变小，关键解也可能经过分数。安全剪枝仅除零、重复状态等经论证规则。
- 正确性由所有树底部二叶运算可先被选中并收缩，归纳覆盖树；反过来每个合并记录对应合法二叉表达式，且每叶被用一次，因此找到24不会引入非法拼接。
手动走一遍
[3,3,8,8]可用8/(3−8/3)=24，若只保留整数中间值会漏解。[1,1,1,1]无解。重复3/8仍是四个独立数字，合并时保留未被选中的另一份。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from fractions import Fraction
def can_make_24(numbers):
if len(numbers) != 4 or any(type(n) is not int for n in numbers):
raise ValueError('expected exactly four integers')
failed = set()
def search(values):
key = tuple(sorted(values))
if key in failed:
return False
if len(values) == 1:
return values[0] == 24
for i in range(len(values)):
for j in range(i + 1, len(values)):
a, b = values[i], values[j]
candidates = {a + b, a * b, a - b, b - a}
if b:
candidates.add(a / b)
if a:
candidates.add(b / a)
remaining = [v for k, v in enumerate(values) if k not in (i, j)]
for result in candidates:
if search(remaining + [result]):
return True
failed.add(key)
return False
return search([Fraction(n) for n in numbers])
复杂度
四个数固定，搜索规模有常数上界；推广m个数每层最多6·C(t,2)分支，粗时间界O(6^(m−1)·m!·(m−1)!/2^(m−1))乘分数运算成本，记忆可减少但不保证多项式。栈O(m)，失败状态缓存随可达数池增长。
易错点与追问
容易失分的边界
- 减除只留一个方向。
- 浮点直接==24或中间取整。
- 按值删除重复数字全部实例。
- 大于24/分数直接剪枝。
继续深挖
- 如何返回一个表达式？
- 要全部表达式时如何定义去重？
- 加入幂运算怎样限制搜索和定义域？
- 数字数量增多有哪些子集DP取舍？
