LeetCode 679. 24 点游戏

Categories:

题目描述
思路分析
1. 解法一：全排列 + 回溯枚举运算符（推荐）
相似题目

题目描述

✅ 679. 24 点游戏

思路分析

解法一：全排列 + 回溯枚举运算符（推荐）

核心思路：

4 张牌共有 4! = 24 种排列，每两个数之间有 4 种运算（+、-、×、÷），共 4³ = 64 种运算符组合。

枚举所有 4! × 4³ = 1536 种情况，对每种情况按固定括号优先级依次计算。

但括号的结合方式也影响结果，例如 (a op b) op (c op d) 与 a op (b op (c op d)) 不同。

因此使用递归回溯：每次从当前数列中选取两个数，用某种运算合并为一个新数，递归处理剩余数字，直到只剩一个数为止。

判断最终结果是否等于 24（使用浮点数误差 1e-6 比较）。

步骤：

将 4 个整数转为浮点数列表。

每次从列表中选取两个数 a 和 b（有序，枚举所有下标对）。

枚举 4 种运算（+、-、×、÷），注意除数不为零时才进行除法。

将运算结果加入列表，移除 a 和 b，递归处理新列表。

递归终止条件：列表只剩一个数，判断是否约等于 24。

复杂度分析：

时间复杂度：O(1)，数字规模固定为 4，枚举总量为常数 1536 种情况。

空间复杂度：O(1)，递归深度最多为 4 层，为常数级别。

class Solution {

    // 浮点比较精度阈值
    private static final double EPS = 1e-6;

    public boolean judgePoint24(int[] cards) {
        List<Double> nums = new ArrayList<>();
        for (int card : cards) {
            nums.add((double) card);
        }
        return backtrack(nums);
    }

    private boolean backtrack(List<Double> nums) {
        if (nums.size() == 1) {
            // 判断最终结果是否等于 24
            return Math.abs(nums.get(0) - 24.0) < EPS;
        }

        int n = nums.size();
        // 枚举所有两个数的有序对 (i, j)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                double a = nums.get(i);
                double b = nums.get(j);

                // 构建去除 i、j 之后的剩余列表
                List<Double> next = new ArrayList<>();
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        next.add(nums.get(k));
                    }
                }

                // 枚举 4 种运算符，将 a op b 的结果加入列表
                for (double result : compute(a, b)) {
                    next.add(result);
                    if (backtrack(next)) {
                        return true;
                    }
                    next.remove(next.size() - 1);
                }
            }
        }
        return false;
    }

    // 返回 a 和 b 所有合法运算结果
    private List<Double> compute(double a, double b) {
        List<Double> results = new ArrayList<>();
        results.add(a + b);
        results.add(a - b);
        results.add(a * b);
        // 除数不为零才进行除法
        if (Math.abs(b) > EPS) {
            results.add(a / b);
        }
        return results;
    }
}

const eps = 1e-6

func judgePoint24(cards []int) bool {
	nums := make([]float64, len(cards))
	for i, card := range cards {
		nums[i] = float64(card)
	}
	return backtrack(nums)
}

func backtrack(nums []float64) bool {
	if len(nums) == 1 {
		// 判断最终结果是否等于 24
		return math.Abs(nums[0]-24.0) < eps
	}

	n := len(nums)
	// 枚举所有两个数的有序对 (i, j)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			a, b := nums[i], nums[j]

			// 构建去除 i、j 之后的剩余列表
			next := make([]float64, 0, n-1)
			for k := 0; k < n; k++ {
				if k != i && k != j {
					next = append(next, nums[k])
				}
			}

			// 枚举 4 种运算符
			for _, result := range compute(a, b) {
				next = append(next, result)
				if backtrack(next) {
					return true
				}
				next = next[:len(next)-1]
			}
		}
	}
	return false
}

// compute 返回 a 和 b 所有合法运算结果
func compute(a, b float64) []float64 {
	results := []float64{a + b, a - b, a * b}
	// 除数不为零才进行除法
	if math.Abs(b) > eps {
		results = append(results, a/b)
	}
	return results
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯、全排列
47. 全排列 II	中等	回溯、去重
282. 给表达式添加运算符	困难	回溯、表达式求值
241. 为运算表达式设计优先级	中等	分治、回溯
932. 漂亮数组	中等	分治、数学
39. 组合总和	中等	回溯、枚举
51. N 皇后	困难	回溯、枚举

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/18803396