题解 | #24点游戏算法#

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] nums = new int[4];
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            for(int i=0;i<4;i++){
                nums[i]=sc.nextInt();
            }
            Stack<String> exps = new Stack<String>();
            System.out.println(dfs(nums, exps));
            // System.out.println(exps); 计算步骤
        }
    }

   private static boolean dfs(int[] nums, Stack<String> exps) {
        int count = 0;
        int val = 0;
        // dfs结束点
        for(int i=0;i<nums.length;i++) {
            if(nums[i]!=-1) {
                count++;
                val= nums[i];
            }
        }
        if(count == 1) {
            if(val == 24) {
                return true;
            } else {
                return false;
            }
        }
        // 遍历两两组合然后继续dfs
        for(int i=0;i<nums.length;i++) {
            for(int j=i+1;j<nums.length;j++) {
                if(nums[i] == -1 || nums[j]==-1) {
                    continue;
                }
                int tempA = nums[i];
                int tempB = nums[j];
                nums[j]=-1;
                // 尝试加法
                nums[i] = tempA + tempB;
                exps.push(tempA + "+" + tempB);
                if(dfs(nums, exps)) {
                    return true;
                }
                exps.pop();
                // 尝试减法
                exps.push(tempA + "-" + tempB);
                nums[i] = tempA - tempB;
                if(dfs(nums, exps)) {
                    return true;
                }
                exps.pop();
                // 尝试被减法
                exps.push(tempB + "-" + tempA);
                nums[i] = tempB - tempA;
                if(dfs(nums, exps)) {
                    return true;
                }
                exps.pop();
                // 尝试乘法
                exps.push(tempA + "*" + tempB);
                nums[i] = tempA * tempB;
                if(dfs(nums, exps)) {
                    return true;
                }
                // 尝试除法
                if(tempB != 0 && tempA%tempB == 0) {
                    exps.pop();
                    exps.push(tempA + "/" + tempB);
                    nums[i] = tempA / tempB;
                    if(dfs(nums, exps)) {
                        return true;
                    }
                }
                // 尝试被除法
                if(tempA != 0 && tempB%tempA == 0) {
                    exps.pop();
                    exps.push(tempB + "/" + tempA);
                    nums[i] = tempB / tempA;
                    if (dfs(nums, exps)) {
                        return true;
                    }
                }
                exps.pop();
                // 选出的俩任意计算方式都不通 恢复数据
                nums[i] = tempA;
                nums[j] = tempB;
            }
        }
        return false;
    }
}