679. 24 点游戏
题目描述
输入长度为 4 的整数数组 cards，每张牌上是 1 到 9 之间的数字。
用这 4 个数各一次，配合加、减、乘、除四种运算和括号组成一个算式，判断能否让算式的值等于 24。
规则如下：除法按实数计算，不取整，例如 4 / (1 - 2 / 3) = 12；每个运算符都必须连接两个运算数，不能把减号当作负号用在单个数前面；不能把几张牌上的数字拼成一个多位数，例如用 1 和 2 拼成 12。
能得到 24 返回 true，否则返回 false。
示例 1
输入：cards = [4,1,8,7] 输出：true
解释：(8 - 4) * (7 - 1) = 24。
示例 2
输入：cards = [1,2,1,2] 输出：false
解释：这四个数怎样组合都得不到 24。
数据范围
cards.length == 41 <= cards[i] <= 9
解题思路
每次从当前数字里任选两个（有序），用一种运算把它们合成一个新数，再放回剩下的数字中，数字个数减一。递归到只剩一个数时，判断它是否等于 24。因为选的是有序对，a - b 与 b - a、a / b 与 b / a 都会被枚举到，括号的所有结合方式也自然被覆盖。实数除法有精度误差，比较时用 1e-6 容差，除数为 0 时跳过除法。
为什么正确
任何时刻，当前列表中的每个数都是若干张原始牌组成的子表达式的值，并且这些子表达式恰好把 4 张牌各用了一次。
复杂度分析
时间 O(1)：4 个数时最多 12*4 * 6*4 * 2*4 种组合；空间 O(1)。
易错点
用整数除法或用 == 24 直接比较浮点数都会出错，例如 8 / (3 - 8 / 3) = 24 需要实数除法和容差比较。还要记得除数为 0 时跳过除法。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def judgePoint24(self, cards: List[int]) -> bool:
def dfs(nums):
if len(nums) == 1:
return abs(nums[0] - 24) < 1e-6
for i in range(len(nums)):
for j in range(len(nums)):
if i == j:
continue
rest = [nums[k] for k in range(len(nums)) if k != i and k != j]
a, b = nums[i], nums[j]
cands = [a + b, a - b, a * b]
if abs(b) > 1e-6:
cands.append(a / b)
for c in cands:
if dfs(rest + [c]):
return True
return False
return dfs(cards)class Solution {
public boolean judgePoint24(int[] cards) {
List<Double> nums = new ArrayList<>();
for (int c : cards) nums.add((double) c);
return dfs(nums);
}
boolean dfs(List<Double> nums) {
if (nums.size() == 1) {
return Math.abs(nums.get(0) - 24) < 1e-6;
}
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
List<Double> rest = new ArrayList<>();
for (int k = 0; k < n; k++) if (k != i && k != j) rest.add(nums.get(k));
double a = nums.get(i), b = nums.get(j);
List<Double> cands = new ArrayList<>(List.of(a + b, a - b, a * b));
if (Math.abs(b) > 1e-6) {
cands.add(a / b);
}
for (double c : cands) {
List<Double> next = new ArrayList<>(rest);
next.add(c);
if (dfs(next)) {
return true;
}
}
}
}
return false;
}
}class Solution {
public:
bool dfs(vector<double> nums) {
if (nums.size() == 1) {
return fabs(nums[0] - 24) < 1e-6;
}
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
vector<double> rest;
for (int k = 0; k < n; k++) if (k != i && k != j) rest.push_back(nums[k]);
double a = nums[i], b = nums[j];
vector<double> cands = {a + b, a - b, a * b};
if (fabs(b) > 1e-6) {
cands.push_back(a / b);
}
for (double c : cands) {
vector<double> next = rest;
next.push_back(c);
if (dfs(next)) {
return true;
}
}
}
}
return false;
}
bool judgePoint24(vector<int>& cards) {
return dfs(vector<double>(cards.begin(), cards.end()));
}
};func judgePoint24(cards []int) bool {
var dfs func(nums []float64) bool
dfs = func(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-6
}
for i := range nums {
for j := range nums {
if i == j {
continue
}
rest := []float64{}
for k := range nums {
if k != i && k != j {
rest = append(rest, nums[k])
}
}
a, b := nums[i], nums[j]
cands := []float64{a + b, a - b, a * b}
if math.Abs(b) > 1e-6 {
cands = append(cands, a/b)
}
for _, c := range cands {
next := append(append([]float64{}, rest...), c)
if dfs(next) {
return true
}
}
}
}
return false
}
nums := make([]float64, len(cards))
for i, c := range cards {
nums[i] = float64(c)
}
return dfs(nums)
}var judgePoint24 = function(cards) {
const dfs = (nums) => {
if (nums.length === 1) {
return Math.abs(nums[0] - 24) < 1e-6;
}
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i === j) {
continue;
}
const rest = nums.filter((_, k) => k !== i && k !== j);
const a = nums[i], b = nums[j];
const cands = [a + b, a - b, a * b];
if (Math.abs(b) > 1e-6) {
cands.push(a / b);
}
for (const c of cands) {
if (dfs([...rest, c])) {
return true;
}
}
}
}
return false;
};
return dfs(cards);
};function judgePoint24(cards: number[]): boolean {
const dfs = (nums: number[]): boolean => {
if (nums.length === 1) {
return Math.abs(nums[0] - 24) < 1e-6;
}
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i === j) {
continue;
}
const rest = nums.filter((_: number, k: number) => k !== i && k !== j);
const a = nums[i], b = nums[j];
const cands = [a + b, a - b, a * b];
if (Math.abs(b) > 1e-6) {
cands.push(a / b);
}
for (const c of cands) {
if (dfs([...rest, c])) {
return true;
}
}
}
}
return false;
};
return dfs(cards);
}