题解 | #24点游戏算法#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String a;
        try {
            a = r.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        char[] chs = a.toCharArray();
        int[] numbs = new int[4];
        int[] computed = new int[4];//默认是0，都没被使用计算过
        int i = 0, j = 0, l = chs.length, n = 0, firstNum;
        boolean twentyFour = false;
        while (i < l) {
            if (chs[i] == ' ') {
                numbs[j++] = n;
                n = 0;
                i++;
                continue;
            }
            n *= 10;
            n += chs[i] - '0';
            if (i == l - 1) numbs[j] = n;
            i++;
        }
        i = 0;
        while (i < 4) {
            firstNum = numbs[i];
            computed[i] =
                1;//第一个数前面不带符号，放入计算式，表示已经计算用过
            if (compute(numbs, computed, firstNum, 24)) {
                twentyFour = true;
                break;
            }
            computed[i] =
                0;//循环没有结束，则表示该数放在第一个计算时得不到24，重置为0，将下一个数放在第一个计算式前计算
            i++;
        }
        System.out.print(twentyFour);
    }

    private static boolean compute(int[] numbs, int[] computed, int firstNum,
                                   int result) {
        boolean allComputed = true, rightFlag = false;
        int i = 0, l = computed.length;
        while (i <
                l) {//所有数都被用了吗，还有数没被用，allComputed就是false
            if (computed[i] == 0) {
                allComputed = false;
                break;
            }
            i++;
        }
        if (allComputed) rightFlag = result ==
                                         firstNum;//当所有数都被计算过，则判断结果是否等于24
        else {
            i = 0;
            while (i < l) {
                if (computed[i] == 1) {//该数已经计算用过，则跳过该次循环
                    i++;
                    continue;
                }
                computed[i] =
                    1;//没被用过，用该数进行四则运算后，递归带入，且该数标识为已经计算用了
                if (compute(numbs, computed, firstNum + numbs[i], result)
                        || compute(numbs, computed, firstNum - numbs[i], result)
                        || compute(numbs, computed, firstNum * numbs[i], result)
                        || numbs[i] != 0 && firstNum % numbs[i] == 0 &&
                        compute(numbs, computed, firstNum / numbs[i], result)) {
                    rightFlag = true;
                    break;
                }
                computed[i] =
                    0;//没有跳出循环吗，则该数重新标识为没被计算用过，继续循环
                i++;
            }
        }
        return rightFlag;
    }
}