24点游戏算法
深度优先搜索回溯约 1133 字大约 4 分钟
HJ67. 24点游戏算法
题目描述
给出 4 个 1~10 的正整数，使用加减乘除运算（+ - * /），每个数字必须且只能用一次，判断是否能组成表达式结果为 24（除法为实数除法）。数字可以通过括号改变优先级。
输入格式
一行 4 个正整数。
输出格式
能组成 24 输出 true，否则输出 false。
示例
示例 1
输入：
7 2 1 10输出：
true示例 2
输入：
1 1 1 1输出：
false解题思路
第一步：理解问题本质
4 个数通过 + - × ÷ 和括号组合，所有数必须用完。等价于：任选两个数做一次运算，结果放回，递归处理 3 个数、2 个数……直到 1 个数时判断是否等于 24。
第二步：暴力解法
枚举所有括号结构（5 种）和所有运算排列，再枚举数字排列。共 4! × 4³ × 5 ≈ 数千种，虽可枚举但代码繁琐。
第三步：DFS + 回溯（最优）
用递归把问题变小：每次从剩余数字中取两个数 a、b，尝试所有二元运算得到结果，放回集合继续递归，直到只剩一个数判断是否等于 24。
关键点：
- 减法/除法需要尝试两个方向：
a-b、b-a、a/b、b/a（分母不为 0）。 - 除法为实数除法，浮点数比较用容差
|x - 24| < 1e-6。 - 分支数有限（4 个数全排列组合），很快结束。
def can_reach_24(nums):
# base case：只剩一个数，它就是整个表达式的值，用容差判浮点误差
if len(nums) == 1:
return abs(nums[0] - 24) < 1e-6
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
# 只取 i<j 的组合，同一对数不会正反各算一遍
a, b = nums[i], nums[j]
rest = [nums[k] for k in range(len(nums)) if k != i and k != j]
# 减、除交换顺序结果不同，四个方向都要列出来
candidates = [a + b, a - b, b - a, a * b]
if b != 0: candidates.append(a / b)
if a != 0: candidates.append(b / a)
for val in candidates:
# 结果放回剩余数字，问题规模从 n 减到 n-1
if can_reach_24(rest + [val]):
return True
return False完整代码实现
import sys
def can_reach_24(nums):
# base case：只剩一个数时它已是整个式子的结果，浮点比较要留容差
if len(nums) == 1:
return abs(nums[0] - 24) < 1e-6
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
# 每轮挑两个数先算，i<j 保证同一对数只被挑一次
a, b = nums[i], nums[j]
rest = [nums[k] for k in range(n) if k != i and k != j]
# 加、乘交换顺序结果不变；减、除必须两个方向都试，否则漏解
candidates = [a + b, a - b, b - a, a * b]
if b != 0:
candidates.append(a / b)
if a != 0:
candidates.append(b / a)
for val in candidates:
# 用掉的 a、b 已被 rest 排除，结果放回去，规模减一
if can_reach_24(rest + [val]):
return True
return False
def solve():
data = sys.stdin.buffer.read().split()
nums = [int(x) for x in data]
print("true" if can_reach_24(nums) else "false")
if __name__ == "__main__":
solve()示例推演
以 3 3 8 8 为例（能组成 24）：
- 取
3和8/3：先算8/3 = 2.666... - 剩
[3, 2.666...] 3 - 2.666... = 0.333...，剩[8, 0.333...]8 / 0.333... = 24✓
表达式为 8 / (3 - 8/3) = 24，输出 true。
再以 1 1 1 1 为例：无论怎么运算，1 与 1 的组合结果最大也就 1×1×1×1=1，永远达不到 24，输出 false。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举括号结构 | O(5·4!·4³) | O(1) | 代码繁琐 |
| DFS + 回溯 | O(4!·4³) | O(4) | 递归深度有限，最优 |
数字仅 4 个，规模恒定，两种都能在常数时间内完成
易错点总结
1. 减法和除法两个方向
a-b 与 b-a、a/b 与 b/a 结果不同，必须都尝试，否则漏解。
2. 除数为 0
a/b 需保证 b != 0，b/a 需保证 a != 0，否则除零报错。
3. 浮点数比较
实数除法产生浮点误差，不能用 == 24，要用容差 abs(x - 24) < 1e-6。
4. 每个数字必须且只能用一次
取走 a、b 后要用 rest 排除它们，不能重复使用。
扩展思考
- 本题可扩展到 n 个数字凑任意目标值，只需调整目标和递归。
- 若需要输出表达式而非判断，可在递归中记录操作历史。