题解 | #24点游戏算法#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            boolean enable = false;  // 保存是否已经找到等于24的表达式
            int[] nums = new int[4];  // 存储4个数字
            boolean[] visit = new boolean[4];  // 存储4个数字的访问状态
            String[] arr = sc.nextLine().trim().split(" ");
            for (int i = 0; i < 4; i++) {
                nums[i] = Integer.parseInt(arr[i]);
            }
            
            for (int i = 0; i < 4; i++) {
                visit[i] = true;
                if (dfs(nums, visit, nums[i])) {
                    enable = true;
                    break;
                }
            }
            System.out.println(enable);
        }
    }
    
    public static boolean dfs(int[] nums, boolean[] visit, int tmp) {
        for (int i = 0; i < nums.length; i++) {
            if (!visit[i]) {
                visit[i] = true;  // 将一个未访问过的位置置于访问状态
                // 递归调用dfs，本质就是暴力搜索
                if (dfs(nums, visit, tmp - nums[i])
                    || dfs(nums, visit, tmp + nums[i])
                    || dfs(nums, visit, tmp * nums[i])
                    || (tmp % nums[i] == 0 && dfs(nums, visit, tmp - nums[i]))) {
                    return true;
                }
                visit[i] = false;  // 回溯
            }
        }
        if (tmp == 24) {
            return true;
        }
        return false;
    }
}