题解 | 24点游戏算法

1. 方针拨乱反正：这里的遍历，不是固定的4个数据的dfs遍历。而是要动态的去遍历，要把中间结果动态的加入到遍历中。前者只能应对不带小括号的情况，后者则适应更一般的规则。
2. 整个过程可以看成‘消二得一’的过程，每次计算都要在待计算的数据中挑选（具体就要枚举了）两个数a和b出来，而挑选剩下的进入到下一层计算中，对a和b进行加减乘除运算，并分别把结果带入到下一层计算中去。所以要带下去四次计算，如果有一次返回true，则迅速返回。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 24点游戏正解
public class Main {

    public static double diff = 1e-6;
    public static double target = 24;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Double> data = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            data.add(in.nextDouble());
        }
        System.out.println(dfs(data));
    }

    public static boolean findFlag = false;

    public static boolean dfs(List<Double> data) {
        if (data.size() == 1) {
            return Math.abs(data.get(0) - target) < diff;
        }
        // 枚举所有的两数计算结果
        for (int i = 0; i < data.size(); i++) {
            for (int j = 0; j < data.size(); j++) {
                if (i == j) {
                    continue;
                }
                // 下一轮计算
                List<Double> nextData = new ArrayList<>();
                for (int k = 0; k < data.size(); k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    nextData.add(data.get(k));
                }

                // 4种计算，并把计算结果依次放到下一轮进行计算。
                // 注意，这里不用考虑什么小括号，因为在当前cal(a,b)的时候，已经是相当于小括号了。
                double a = data.get(i);
                double b = data.get(j);
                List<Double> ret = new ArrayList<>();
                ret.add(a + b);
                ret.add(a - b);
                ret.add(a * b);
                ret.add(a / b);
                for (int k = 0; k < ret.size(); k++) {
                    double r = ret.get(k);
                    nextData.add(r);
                    if (dfs(nextData)) {
                        return true;
                    }
                    // 回溯
                    nextData.remove(nextData.size() - 1);
                }
            }
        }
        return false;
    }
}