题解 | 24点游戏算法

import java.util.*;
import java.io.*;

public class Main {
    static int[] nums = new int[4];
    static int[] perm = new int[4]; // 存储当前排列
    static boolean[] visit = new boolean[4];
    static boolean found = false;
    private static final double EPSILON = 1e-6;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            found = false;
            String[] a = in.nextLine().split(" ");
            for (int i = 0; i < 4; i++) {
                nums[i] = Integer.parseInt(a[i]);
            }
            
            // 对数组排序，便于后续去重处理
            Arrays.sort(nums);
            generatePermutations(0);
            
            System.out.println(found);
        }
        in.close();
    }

    // 生成所有可能的排列（修复重复数字处理）
    static void generatePermutations(int index) {
        if (found) return;
        
        if (index == 4) {
            double x= 24;
            dfs((double)perm[0], 0, x);
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            if (!visit[i]) {
                // 关键修复：仅当相同数字的前一个已被使用时，才允许使用当前数字
                // 避免重复排列，但保留有效组合
                if (i > 0 && nums[i] == nums[i-1] && !visit[i-1]) {
                    continue;
                }
                visit[i] = true;
                perm[index] = nums[i];
                generatePermutations(index + 1);
                visit[i] = false;
            }
        }
    }

    // DFS计算逻辑保持不变
    static void dfs(double last, int i, double target) {
        if (found) return;
        
        if (i == 3) {
            if (Math.abs(last - target) < EPSILON) {
                found = true;
            }
            return;
        }
        
        int next = perm[i + 1];
        
        if(i==1&&last!=0){
            dfs(perm[i + 1]+perm[i + 2], i + 2, target/last);
            if (found) return;
            dfs(perm[i + 1]-perm[i + 2], i + 2, target/last);
            if (found) return;    
        }
        
        dfs(last + next, i + 1, target);
        if (found) return;
        
        dfs(last - next, i + 1, target);
        if (found) return;
        
        dfs(next - last, i + 1, target);
        if (found) return;
        
        dfs(last * next, i + 1, target);
        if (found) return;
        
        if (Math.abs(next) > EPSILON) {
            dfs(last / next, i + 1, target);
            if (found) return;
        }
        
        if (Math.abs(last) > EPSILON) {
            dfs(next / last, i + 1, target);
            if (found) return;
        }
    }
}

写一下评论区都没完善的思路：

1 计算过程可能有小数

2 没有考虑括号优先级

3 题目数组顺序可以改变

用排列+搜索+特殊处理括号优先级