lc679. 24 点游戏（回溯）

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:

输入: [1, 2, 1, 2]
输出: False
注意:

除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

class Solution {
    /**
    每次选出两个数字进行组合运算(+,-,*,/),加法乘法不用考虑顺序，然后继续选出两个数进行组合
    直到list只剩一个数，判断与24的误差是否 < 1e-6
    细节：我们可以copy一个数组删除选中的两个数字，然后算这两个数的+,-,*,/,处理完一种运算继续回溯回来处理下一个
    为了剪枝，我们可以定义一个boolean变量，利用||的短路性，当有一条支路返回true时无需判断其他支路
     */
    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int i = 0; i < 4; ++i) {
            list.add((double)cards[i]);
        }
        return backtracking(list);
    }
    public boolean backtracking(List<Double> list) {
        if (list.size() == 1) return Math.abs(list.get(0) - 24) < 1e-6;
        boolean isLegal = false;
        for (int i = 0; i < list.size(); ++i) 
            for (int j = i + 1; j < list.size(); ++j) {
                List<Double> copy = new ArrayList<>(list);
                //注意这里先移出j不然先移除i，j不一样会越界
                double a = copy.remove(j), b = copy.remove(i);
                copy.add(a + b);                                //加法
                isLegal = isLegal || backtracking(copy);
                copy.set(copy.size() - 1, a - b);               //a-b
                isLegal = isLegal || backtracking(copy);
                copy.set(copy.size() - 1, b - a);               //b-a
                isLegal = isLegal || backtracking(copy);
                copy.set(copy.size() - 1, b * a);               //a*b
                isLegal = isLegal || backtracking(copy);        
                copy.set(copy.size() - 1, a / b);               //a/b
                isLegal = isLegal || backtracking(copy);      
                copy.set(copy.size() - 1, b / a);               //b/a
                isLegal = isLegal || backtracking(copy);
                if(isLegal) return true;
            }
        return false;
    }
}