题解 | #24点游戏算法#

import java.util.*;

public class Main {
    public static int n = 4;//参与运算的数字数量
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       

        while (in.hasNext()) {
            String[] arrStr = in.nextLine().split(" ");
            int[] num = new int[n];
            for (int i = 0; i < n; i++) {
                num[i] = Integer.valueOf(arrStr[i]);
            }
            
            //判断某个数据是否已经被使用
            boolean[] visited = new boolean[n];
            boolean flag = false; //结果存储
            flag = dfs(0 , 0, num, visited);
            System.out.println(flag);
        }
    }

    /**
    通过深度优先搜索的方法，考察所有可能的情况，若出现
    count 记录参与运算的数字个数
    sum 表示当前运算结果，为double型，以免出现整数运算取整的情况
    num 参与运算的数字集
    visited 判断当前数字是否被使用过
     */
    private static boolean dfs(int count, double sum, int[] num, boolean[] visited) {
        //输入的4个数字都已经参与运算, 递归终止
        if (count == n) {
            return sum == 24;
        } else {
            count++;
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    //参与运算 - +，-，*，/
                    visited[i] = true; //参与运算
                    if(dfs(count, sum + num[i], num, visited) 
                    || dfs(count, sum - num[i], num, visited)
                    || dfs(count, sum * num[i], num, visited)
                    || num[i] != 0 && dfs(count, sum / num[i], num, visited)){ //考虑除数为0的情况
                        return true;
                    }
                    visited[i] = false;//溯回
                }
            }
            return false;
        }
    }

}