题解 | 24点游戏算法

基于DFS算法，并考虑了括号特殊情况（即count == 2时的情况），详见代码：

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

/*
    知识点：递归、深度优先搜索、回溯算法
*/
public class Main {

    static int[] nums = new int[4];
    static int[] visit = new int[4];
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            String[] numstr = str.split(" ");
            for (int i = 0; i < 4; i++) {
                nums[i] = Integer.parseInt(numstr[i]); // 读取数字
            }
            System.out.println(dfs(0));
        }
    }

    public static boolean dfs(int temp) {
        for (int i = 0; i < nums.length; i++) {
            if (visit[i] == 0) { // 如果是未使用的数字
                if (count++ == 2) {
                    int a = 0, b = 0;
                    for (int j = 0; j < 4; j++) {
                        if (visit[j] == 0) {
                            if (a == 0) {
                                a = nums[j];
                            } else {
                                b = nums[j];
                            }
                        }
                    }
                    for (double n : getAnyRes(a, b)) {
                        for (double m : getAnyRes(temp, n)) {
                            if (m == 24) {
                                return true;
                            }
                        }
                    }
                }
                visit[i] = 1; // 标记为已使用
                if (dfs(temp + nums[i]) // 递归判断
                        || dfs(temp - nums[i])
                        || dfs(temp * nums[i])
                        || (temp % nums[i] == 0 && dfs(temp / nums[i]))) {
                    // 如果存在满足条件的，终止循环
                    return true;
                }
                // 不存在满足条件的，说明当前的数字顺序不符要求，进行回溯，把标记重置为0
                visit[i] = 0;
                count--;
            }
        }
        // 数字都已使用且结果为24，返回真
        if (temp == 24) {
            return true;
        }
        // 不存在24，返回假
        return false;
    }

    private static List<Double> getAnyRes(double a, double b) {
        List<Double> res = new ArrayList<Double>();
        res.add(a + b);
        res.add(a * b);
        res.add(a - b);
        res.add(b - a);
        if (a != 0) {
            res.add(b / a);
        }
        if (b != 0) {
            res.add(a / b);
        }
        return res;
    }
}