题解 | #24点游戏算法#回溯思路

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(
            System.in); // 创建一个Scanner对象，用于从控制台读取输入

        // 读取用户输入的四个整数
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        int num3 = scanner.nextInt();
        int num4 = scanner.nextInt();

        scanner.close(); // 关闭Scanner对象

        // 调用canGetTwentyFour方法检查是否可以得到24点
        boolean canGet24 = canGetTwentyFour(num1, num2, num3, num4);

        // 输出结果，如果可以得到24点则输出true，否则输出false
        System.out.println(canGet24);
    }

    // 检查是否可以通过加减乘除运算得到目标值target，使用给定的数字numbers
    private static boolean canGetTwentyFour(int... numbers) {
        boolean [] visited = new boolean[] {false, false, false, false};
        return solve(numbers,  24.0,
                     0.0, visited);  // 调用solve方法，从第一个数字开始，目标值为24，当前计算结果为0
    }

    // 递归方法，用于解决24点问题
    private static boolean solve(int[] numbers, double target,
                                 double current, boolean[] visited) {
        // 如果已经使用了所有的数字
        if (visitedisfull(visited)) {
            // 检查当前计算结果是否接近目标值（允许一定的浮点数误差）
            return Math.abs(current - target) < 1e-6;
        }

        // 遍历所有可能的数字对
        for (int i = 0; i < numbers.length; i++) {
            if (!visited[i]) {
                //标记访问
                visited[i] = true;

                double nextCurrent = performOperation(current, numbers[i], '+');
                if (solve(numbers,  target, nextCurrent, visited)) {
                    return true;
                }


                //减法a-b，b-a是不一样的，所以执行两次
                nextCurrent = performOperation(current, numbers[i], '-');
                if (solve(numbers,  target, nextCurrent, visited)) {
                    return true;
                }

                nextCurrent = performOperation(numbers[i], current, '-');
                if (solve(numbers,  target, nextCurrent, visited)) {
                    return true;
                }


                nextCurrent = performOperation(current, numbers[i], '*');
                if (solve(numbers,  target, nextCurrent, visited)) {
                    return true;
                }

                //除法a/b，b/a是不一样的，所以执行两次
                nextCurrent = performOperation(current, numbers[i], '/');
                if (solve(numbers,  target, nextCurrent, visited)) {
                    return true;
                }
                if (Math.abs(current - 0.0) > 1e-6) {
                    nextCurrent = performOperation(numbers[i], current,  '/');
                    if (solve(numbers,  target, nextCurrent, visited)) {
                        return true;
                    }
                }
                //回溯
                visited[i] = false;
            }

        }


        // 如果所有组合都尝试完了还找不到解，则返回false
        return false;
    }


    private static boolean visitedisfull(boolean [] visited) {

        for (boolean b : visited) {
            if (!b)return false;
        }
        return true;
    }

// 执行指定的运算
    private static double performOperation(double a, double b, char op) {
        if (op == '+')
            return a + b;
        else if (op == '-')
            return a - b;
        else if (op == '*')
            return a * b;
        else
            return  a / b;


    }
}