递归+回溯+DFS（有分析带括号情况）

偷得别人答案，但是那个老哥没有解决所有情况。

本代码完美解决题目问题，适应所有情况。

同时追溯显示了四个数字的运算情况。（记得去掉输出代码的//）

只能说递归还是好用的 虽然空间消耗大，但是代码还算简洁、整齐。

很适合我这种强迫症，O(∩_∩)O哈哈~。

import java.util.*;
import java.io.*;
public class Main {
    private static int[] nums = new int[4];
    private static boolean[] visit = new boolean[4];
    private static boolean[] visit2 = new boolean[4];
    private static int flag = 0;
    private static int flag2 = 0;
  	//显示四个数字的 出现顺序 和各个运算符
    private static String z = "", x = "", c = "", v = "";
  	//显示四个数字的 出现顺序 和各个运算符， b为两括号相运算的实际情况。
    private static String z2 = "", x2 = "", c2 = "", v2 = "", b = "";
    private static int count = 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]);
            dfs(0, 0);
            dfs3(0, 0, 0, 0);

            System.out.println( flag == 1 || flag2 == 1);
            //System.out.println( z + " / " + x + " / " + c + " / " + v );
            //System.out.println( z2 + " / " + x2 + " / " + c2 + " / " + v2 );
            //System.out.println(b);
            //System.out.println( count );
        }

    }

    // tmp是前面n个数字运算结果，u表示已经使用了多少个数字。 不考虑括号。
    static boolean dfs(int u, float tmp) {
        //count++;
        //System.out.println("1");
        // 递归终止条件：已经使用了数组四个元素，同时结果为24，满足题意
        if (tmp == 24 && u == 4) {
            flag = 1;
            return true;
        }

        for (int i = 0; i < 4; i ++) {
            if (visit[i] ==
                    false) {    //没访问过才执行。 都访问过了就跳过此if代码块，还不达成条件 就返回false。
                visit[i] = true;
                // 加减乘除当前数字num[i]
                if ( dfs(u + 1, tmp +
                         nums[i]) ) {  //四个数字运算完后不符合 返回false，不执行此if代码块
                    z += "(" + u + ")" + "+" + nums[i] + " ";
                    return true;    //退出语句。 满足递归终止条件， 即满足if ， 返回true 一路退出递归。
                }
                if (tmp != 0) {
                    if (dfs(u + 1, tmp - nums[i])) {
                        x += "(" + u + ")" + "-" + nums[i] + " ";
                        return true;
                    }
                    if (dfs(u + 1, tmp * nums[i])) {
                        c += "(" + u + ")" + "*" + nums[i] + " ";
                        return true;
                    }
                    if (dfs(u + 1, tmp / nums[i])) {
                        v += "(" + u + ")" + "/" + nums[i] + " ";
                        return true;
                    }
                }
                /*if( dfs(u + 1, tmp + nums[i]) ||
                        dfs(u + 1, tmp - nums[i])  ||
                        dfs(u + 1,tmp * nums[i]) ||
                        dfs(u + 1, tmp / nums[i])){
                    return true;
                }*/
                // 相当于回溯。 当前四个数字的组合未能符合 则回溯
                visit[i] = false;
            }
        }
        return false;   //if语句没通过 试试其他运算了
    }

    static boolean dfs2(int u, float tmp1, float tmp2, float tmp) {
        for (int i = 0; i < 4; i ++) {
            tmp1 += nums[i];
            visit2[i] = true;
            for (int j = i + 1; j < 4; j ++) {
                tmp1 += nums[j];
                visit2[j] = true;

                for (int x = 0; x < 4; x ++) {
                    if (visit2[x] == false) {
                        tmp2 += nums[x];
                    }
                }
                tmp = tmp1 + tmp2;
                if (tmp == 24) {
                    return true;
                }
            }
        }

        return false;
    }

  	//考虑有括号的情况
    static boolean dfs3(int u, float tmp1, float tmp2, float tmp) {
        // 递归终止条件：已经使用了数组四个元素,两两运算，再互相运算同时结果为24，满足题意
        if (tmp1 + tmp2 == 24 && u == 4) {
            flag2 = 1;
            b += tmp1 + "+" + tmp2;
            return true;
        }
        if (tmp1 - tmp2 == 24 && u == 4) {
            flag2 = 1;
            b += tmp1 + "-" + tmp2;
            return true;
        }
        if (tmp1 * tmp2 == 24 && u == 4) {
            flag2 = 1;
            b += tmp1 + "*" + tmp2;
            return true;
        }
        if (tmp1 / tmp2 == 24 && u == 4) {
            flag2 = 1;
            b += tmp1 + "/" + tmp2;
            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,
                             0)) {   //四个数字运算完后不符合 返回false，不执行此if代码块
                        z2 += "(" + u + ")" + "+" + nums[i] + " ";
                        return true;    //退出语句。
                    }
                    if (tmp1 != 0) {
                        if (dfs3(u + 1, tmp1 - nums[i], 0, 0)) {
                            x2 += "(" + u + ")" + "-" + nums[i] + " ";
                            return true;
                        }
                        if (dfs3(u + 1, tmp1 * nums[i], 0, 0)) {
                            c2 += "(" + u + ")" + "*" + nums[i] + " ";
                            return true;
                        }
                        if (dfs3(u + 1, tmp1 / nums[i], 0, 0)) {
                            v2 += "(" + u + ")" + "/" + nums[i] + " ";
                            return true;
                        }
                    }
                } else {	//选好后两个数字，进行运算。
                    if (dfs3(u + 1, tmp1, tmp2 + nums[i],
                             0)) {   //四个数字运算完后不符合 返回false，不执行此if代码块
                        z2 += "(" + u + ")" + "+" + nums[i] + " ";
                        return true;    //退出语句。
                    }
                    if (tmp2 != 0) {
                        if (dfs3(u + 1, tmp1, tmp2 - nums[i], 0)) {
                            x2 += "(" + u + ")" + "-" + nums[i] + " ";
                            return true;
                        }
                        if (dfs3(u + 1, tmp1, tmp2 * nums[i], 0)) {
                            c2 += "(" + u + ")" + "*" + nums[i] + " ";
                            return true;
                        }
                        if (dfs3(u + 1, tmp1, tmp2 / nums[i], 0)) {
                            v2 += "(" + u + ")" + "/" + nums[i] + " ";
                            return true;
                        }
                    }

                }
                // 相当于回溯
                visit2[i] = false;
            }
        }
        return false;
    }
}