题解 | #HJ067 24点游戏算法#

import java.util.Scanner;

/**
 * HJ67 24点游戏算法 - 中等
 */ 
public class HJ067 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            boolean result = getResult(str);
            System.out.println(result);
        }
        sc.close();
    }

    private static boolean getResult(String str) {
        String[] numstr = str.split(" ");
        int[] nums = new int[4]; // 存放数字
        int[] visit = new int[4]; // 存放对应位置数字的使用状态（1代表已使用）
        boolean flag = false;
        for (int i = 0; i < 4; i++) {
            nums[i] = Integer.parseInt(numstr[i]); // 读取数字
        }
        for (int i = 0; i < 4; i++) {
            visit[i] = 1; // 把当前数字标记为已使用
            if (dfs(nums, visit, nums[i])) { // 进入递归
                flag = true;
                break;
            }
        }
        return flag;
    }

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

}