LeetCode 679：24 点游戏（回溯）

文章目录

题目示例注意代码（回溯）

题目

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

示例

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

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

注意

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

代码（回溯）

可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。

class Solution { static final double THRESHOLD = 1e-6; static final int TARGET = 24; static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3; public boolean judgePoint24(int[] nums) { List<Double> list = new ArrayList<>(); for(int n : nums){ list.add((double)n); } return judge(list); } public boolean judge(List<Double> list){ if(list.size() <= 0){ return false; } if(list.size() == 1){ return Math.abs(list.get(0)-TARGET) < THRESHOLD; } int size = list.size(); for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ if(i != j){ List<Double> temp = new ArrayList<>(); for(int m=0;m<size;m++){ if(m != i && m != j){ temp.add(list.get(m)); } } double a = list.get(i); double b = list.get(j); for(int n=0;n<4;n++){ if(n < 2 && i > j){ continue; } if(n == ADD){ temp.add(a+b); }else if(n == MULTIPLY){ temp.add(a*b); }else if(n == SUBTRACT){ temp.add(a-b); }else{ if(Math.abs(b) >= THRESHOLD){ temp.add(a/b); }else{ continue; } } if(judge(temp)){ return true; } temp.remove(temp.size() - 1); } } } } return false; } }

原文