24点游戏

679. 24 点游戏

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

示例 1:

1
2
3

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

示例 2:

1 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 。

一共有 4 个数和 3 个运算操作，因此可能性并不多。

首先从 4 个数字中有序取出两个数字共 4 * 3 = 12 种选法，再选择 4 种运算中的一种，将运算的结果取代选出的两个数字。

在剩下的 3 个数字中有序取出两个数字共 3 * 2 = 6 种选法，再选择 4 种运算中的一种，将运算的结果取代选出的两个数字。

最后剩下两个数字，有两种不同的顺序，并选择 4 种运算之一。

总共有 12 * 4 * 6 * 4 * 2 * 4 = 9216 种可能。

我们直接使用暴力方法来求解，用一个列表存储全部数字，每次从列表中选出 2 个数字，再选择 1 种运算操作，用计算的结果取代选出的 2 个数字。重复以上步骤，直到最后剩下一个数字，判断它是否等于 24 即可。

注意到除法运算为实数除法，结果为浮点数，因此在列表中应该全部存储浮点数。两个浮点数差值小于 1e-6 时可认为它们相等。同时，在进行除法运算时，除数不能为 0 ，遇到这种情况我们可以直接排除。

加法和乘法都满足交换律，对于选出的 2 个数字不需要考虑不同的顺序，在第二次运算时直接跳过。

class Solution {
    private final int TARGET = 24;
    private final double EPSILON = 1e-6;
    private final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        //将所有数字转为 double 并存进list
        for(int num : nums){
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list){
        if(list.size() == 0){
            return false;
        }
        //列表中只剩一个数字，判断它是否等于 24
        if(list.size() == 1){
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }
        int size = list.size();
		// 有序选出 i，j 位置的两个数
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                //选出同一个数
                if(i == j){
                    continue;
                }
                List<Double> list2 = new ArrayList<>();
                //保存除 i，j 位置的元素
                for(int k = 0; k < size; k++){
                    if(k != i && k != j){
                        list2.add(list.get(k));
                    }
                }
				//选出一种运算
                for(int k = 0; k < 4; k++){
                    //如果是加或乘运算，且这是第二次选中 i 和 j
                    if(k < 2 && i > j){
                        continue;
                    }
					//计算结果
                    if(k == ADD){
                        list2.add(list.get(i) + list.get(j));
                    }else if(k == MULTIPLY){
                        list2.add(list.get(i) * list.get(j));
                    }else if(k == SUBTRACT){
                        list2.add(list.get(i) - list.get(j));
                    }else if(k == DIVIDE){
                        //跳过除数为 0 的情况
                        if(Math.abs(list.get(j)) < EPSILON){
                            continue;
                        }else{
                            list2.add(list.get(i) / list.get(j));
                        }
                    }
					//继续选出两个数字并计算，如果得到结果，返回 true
                    if(solve(list2)){
                        return true;
                    }
					// list 不能得到 24点，删除加入的元素，并尝试下一种运算
                    list2.remove(list2.size() - 1);
                }
            }
        }
        return false;
    }
}

时间复杂度O(1)，空间复杂度O(1)。