题解 | #24点游戏算法#

方法一：DFS+DFS

基于某位老哥的答案，优化的。

极简，完美解决所有情况。包括有括号的。不如说就是基于有括号的情况。

package com.company.huwweiExam;

import java.util.*;
import java.io.*;

public class Main {
    private static int[] nums = new int[4];
    private static boolean[] visit2 = new boolean[4];
    private static int flag2 = 0;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String[] a = in.nextLine().split(" ");
            for (int i = 0; i < 4; i++)
                nums[i] = Integer.parseInt(a[i]);
            dfs3(0, 0, 0);
            System.out.println( flag2 == 1);

            flag2 = 0;
            visit2 = new boolean[4];
        }
    }


    private static boolean dfs3(int u, float tmp1, float tmp2) {
        // 递归终止条件：已经使用了数组四个元素,两两运算，再互相运算同时结果为24，满足题意
        if (tmp1 + tmp2 == 24 ||
                tmp1 - tmp2 == 24 ||
                tmp1 * tmp2 == 24 ||
                tmp1 / tmp2 == 24 &&
                u == 4) {
            flag2 = 1;      //成功找到运算组合
            return true;
        }

        for (int i = 0; i < 4; i++) {
            if (visit2[i] == false) {   //当前数字没访问过
                visit2[i] = true;       //当前数字设为访问过
                // 加减乘除当前数字num[i]
                if (u < 2) {   //对前两个数字运算
                    if (dfs3(u + 1, tmp1 + nums[i], 0)) {    //四个数字运算完后不符合 返回false，不执行此if代码块
                        return true;    //退出语句。
                    }
                    if (tmp1!=0){   //0可以与后面做+，但不能与后面的数字做-*/。
                        if (dfs3(u + 1, tmp1 - nums[i], 0) ||
                                dfs3(u + 1, tmp1 * nums[i], 0) ||
                                dfs3(u + 1, tmp1 / nums[i], 0)){
                            return true;    //退出语句。
                        }
                    }
                } else {   //对后两个数字运算
                    if (dfs3(u + 1, tmp1, tmp2 + nums[i])) {    //四个数字运算完后不符合 返回false，不执行此if代码块
                        return true;    //退出语句。
                    }
                    if (tmp2!=0){
                        if (dfs3(u + 1, tmp1, tmp2 - nums[i]) ||
                                dfs3(u + 1, tmp1, tmp2 * nums[i]) ||
                                dfs3(u + 1, tmp1, tmp2 / nums[i])){
                            return true;    //退出语句。
                        }
                    }
                }
                // 四种运算都失败了，当前数字设为没访问过，相当于回溯
                visit2[i] = false;
            }
        }
        //四位数字都运算过了，且失败了。
        return false;
    }
}