题解 | #24点游戏算法#

首先感谢大神提出的问题，我个人一开始也忽略了两两组合的情况：

https://blog.nowcoder.net/n/d8686854e48b4d59bc9813f450e16a13?f=comment

针对上面大神的答案，我个人有两个改进思路：

1、整体拆成两部分判断：逐个计算判断与两两计算判断，且两两计算判断只考虑(n1 +/- n2) */÷ (n3 +/- n4) = 24这种情况，即括号里面的计算如果是乘或除，括号就没必要了，在逐个判断时就已经包括进去这种情况了；括号外面如果是加或减，两个括号就都没必要了，同上。（在括号内做减法时，只考虑n1-n2的情况，忽略n2-n1，与此同时忽略相减后的负号，因为最后乘或除能得到-24，就一定能得到24。这样只需要考虑（01、23）（02、13）（03、12）三种组合情况即可。）

2、全程整数运算，除法之前先判断能否整除，不考虑产生小数的情况（针对1/2*6*8=24的情况，后面轮询到1*6*8/2=24也能判断成功，所以前面可以不做1/2这一分支。）

import java.util.*;

public class Main {
    
    static int[] arr = new int[4];// 用于接收传入的4个整数
    static boolean[] used = new boolean[4];// 用于判断对应序号的整数有没有被使用。
    static int count = 0;
    int tmp = 0;
    
    public static void main(String[] args) {

         Scanner scanner = new Scanner(System.in);
         
         arr[0] = scanner.nextInt();
         arr[1] = scanner.nextInt();
         arr[2] = scanner.nextInt();
         arr[3] = scanner.nextInt();
         
         
         if (help2(0, 0, 0)) {
             System.out.println(true);
         } else {// 计算 (n1 +/- n2) */÷ (n3 +/- n4) = 24的情况
             System.out.println(help22(0, 0, 0, 0 ,0));
         }
    }

    /**
     * 正向逐个处理
     */
    public static boolean help2 (int n1, int flag, int n2) {// 0-初始; 1-加; 2-减; 3-乘; 4-除
        
        if (count == 1) {
            n1 = n2;
        } else {
            if (flag == 1) {
                n1 = n1 + n2;
            } else if (flag == 2) {
                n1 = n1 - n2;
            } else if (flag == 3) {
                n1 = n1 * n2;
            } else if (flag == 4) {
                n1 = n1 / n2;
            } 
        }
        
        if (count < 4) {
            for (int i=0; i<4; i++) {// i:取数
                if (used[i]) {
                    continue;
                }
                count ++;
                used[i] = true;
                for (int j=4; j>0; j--) {// j:四则运算标志
                    if (j == 4) {
                        if (n1 % arr[i] == 0) {
                            if (help2(n1, j, arr[i])) {
                                return true;
                            }
                        }
                    } else {
                        if (help2(n1, j, arr[i])) {
                            return true;
                        }
                    }
                }
                count --;
                used[i] = false;
            }
        } else if (count == 4 && n1 ==24) {
            return true;
        }
        
        return false;
    }
    
    /**
     * 
     * @param n1    与arr[0]计算的下标值
     * @param n2    不与arr[0]计算的下标值之一
     * @param n3    不与arr[0]计算的下标值之一
     * @param flag1    arr[0]与arr[n1]的运算(0-初始化; 1-加; 2-减)
     * @param flag2 另外两个值的运算(0-初始化; 1-加; 2-减)
     * @return
     */
    public static boolean help22(int n1, int n2, int n3, int flag1, int flag2) {
        
        if (flag1 == 0 && flag2 ==0) {
            for (int f1=1; f1<=2; f1++) {// flag1
                for (int f2=1; f2<=2; f2++) {// flag2
                    if (help22(1, 2, 3, f1, f2)) {
                        return true;
                    }
                    if (help22(2, 1, 3, f1, f2)) {
                        return true;
                    }
                    if (help22(3, 1, 2, f1, f2)) {
                        return true;
                    }
                }
            }
        } else {
            int tmp1 = 0, tmp2 = 0;
            if (flag1 == 1) {
                tmp1 = arr[0] + arr[n1];
            } else if (flag1 == 2) {
                tmp1 = arr[0] - arr[n1];
                if (tmp1 < 0) {
                    tmp1 = tmp1 * -1;
                }
            }
            
            if (flag2 == 1) {
                tmp2 = arr[n2] + arr[n3];
            } else if (flag2 == 2) {
                tmp2 = arr[n2] - arr[n3];
                if (tmp2 < 0) {
                    tmp2 = tmp2 * -1;
                }
            }
            
            if (tmp1 * tmp2 == 24
                    || (tmp2 != 0 && tmp1 % tmp2 == 0 && tmp1 / tmp2 == 24)
                    || (tmp1 != 0 && tmp2 % tmp1 == 0 && tmp2 / tmp1 == 24)) {
                return true;
            }
            
        }
        return false;
    }

}