题解 | #24点游戏算法#

参考大佬的算法，做了下修改：

通过方法compute(a,b)来计算生存所有a和b可能的运算结果，所有结果用一个栈来存储；

分别从nums[i]中取出1、2、3、4个数进行运算。

方法compute24(nums, used, result)中，nums是输入的4个数字数组，used是BitSet用于记录4个数字的占用情况，result是记录当前已经占用的数字计算生成的结果。

采用递归的思想：

1. （递归回归条件）如果nums[]数组已经被占用完，而且计算结果result是24，则返回true，否则进行下一步：
2. 先从nums[]中取出一个数nums[i]，并记录占用情况used.set(i)；
3. 将步骤1中的值记为result，递归调用compute24，如果能够获得24的结果，则返回true，否则返回false；

在递归中，需要分情况处理剩下的1-3个数字：

如果还剩1个，或者还剩3个数字：

1. 遍历未使用的数字，并标记其占用，与result计算结果获得results栈；
2. 遍历该栈的所有值，将该值作为新的result递归调用，判断是否能够得到24，是的话返回true，否则的话返回false。

如果还剩2个数字：

1. 取出剩下的两个数字nums[i]、nums[j]；
2. 先计算nums[i]与nums[j]的所有结果，然后遍历该结果ans1，计算ans1与当前result值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
3. 再计算nums[i]与result的所有结果，然后遍历该结果ans1，计算ans1与nums[j]值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
4. 最后计算nums[j]与result的所有结果，然后遍历该结果ans1，计算ans1与nums[i]值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
5. 所有组合计算完成，没有得到24，返回false；

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = new int[4];
        BitSet used = new BitSet(4);
        for(int i = 0; i < 4; i++){
            nums[i] = in.nextInt();
            used.clear(i);
        }
        System.out.println(compute24(nums, used, 0));
    }

    public static boolean compute24(int[] nums, BitSet used, double result){
        boolean got24 = result == 24 && used.cardinality() == 4;
        if(got24){
            return true;
        }
        // 首次进行运算，一个数字都还没使用
        if(used.cardinality() == 0){
            for(int i = 0; i < 4; i++){
                used.set(i);
                if(compute24(nums, used, nums[i])){ // 把nums[i]单独作为结果，对其他数字进行递归运算
                    return true;
                }
                used.clear(i);
            }
            return false; // 循环四个数字之后依然不能得到24，则失败
        }
        else if(used.cardinality() == 1 || used.cardinality() == 3){
            int unusedIndex = -1;
            while((unusedIndex = used.nextClearBit(unusedIndex + 1)) != -1 && unusedIndex < 4){
                used.set(unusedIndex); // 将找到的第一个未使用的值设为已使用
                Stack<Double> results = compute(nums[unusedIndex], result); // 将未使用的nums[unusedIndex]和result进行运算，获得所有可能的运算结果
                while(!results.isEmpty()){
                    if(compute24(nums, used, results.pop())){ // 递归遍历运算结果，判断是否能够得到24
                        return true;
                    }
                }
                used.clear(unusedIndex); // 如果未找到能够凑成24的运算，那么清除当前的nums[unusedIndex]使用占用
            }
        }
        // 对于已经使用2个数字的情况下进行处理
        else if(used.cardinality() == 2){
            // 找出两个未使用的数字下标
            int i = used.nextClearBit(0);
            int j = used.nextClearBit(i + 1);
            // 1. 先考虑nums[i]、nums[j]两者的所有运算结果
            Stack<Double> ans1 = compute(nums[i], nums[j]);
            while(!ans1.isEmpty()){ // 遍历每个运算结果
                // 将该计算结果取出来和result做运算
                Stack<Double> ans2 = compute(ans1.pop(), result);
                while(!ans2.isEmpty()){
                    if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
                        return true;
                    }
                }
            }
            // 2. 考虑nums[i]、result计算两者的所有运算结果
            ans1 = compute(nums[i], result);
            while(!ans1.isEmpty()){ // 遍历每个运算结果
                // 将该计算结果取出来和nums[j]做运算
                Stack<Double> ans2 = compute(ans1.pop(), nums[j]);
                while(!ans2.isEmpty()){
                    if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
                        return true;
                    }
                }
            }
            // 3. 考虑nums[j]、result计算两者的所有运算结果
            ans1 = compute(nums[j], result);
            while(!ans1.isEmpty()){ // 遍历每个运算结果
                // 将该计算结果取出来和nums[i]做运算
                Stack<Double> ans2 = compute(ans1.pop(), nums[i]);
                while(!ans2.isEmpty()){
                    if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
                        return true;
                    }
                }
            }
        }
        // 最后所有情况都尝试了一遍都未找到24的运算结果，返回失败
        return false;
    }

    public static Stack<Double> compute(double a, double b){
        Stack<Double> stack = new Stack<>();
        stack.add(a - b);
        stack.add(b - a);
        stack.add(b + a);
        stack.add(b * a);
        if(a != 0){
            stack.add(a/b);
        }
        if(b!=0){
            stack.add(b/a);
        }
        return stack;
    }
}