题目链接

题目描述

给定一个长度为 4 的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值 24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
- 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
- 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
- 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

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

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

提示:

cards.length == 4
1 <= cards[i] <= 9

解题思路

方法一：回溯法
一共有 4 个数和 3 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
然后在剩下的 3 个数字中有序地选出 2 个数字，共有 3×2=6 种选法，并选择 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 2 个数字。
最后剩下 2 个数字，有 2 种不同的顺序，并选择 4 种运算操作之一。
因此，一共有 12×4×6×4×2×4=9216 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10−6 可以认为是相等。
进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10−6 时，可以认为该数字等于 0。

还有一个可以优化的点。

加法和乘法都满足交换律，因此如果选择的运算操作是加法或乘法，则对于选出的 2 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。

class Solution {
  static final int TARGET = 24;
  static final double EPSILON = 1e-6;
  static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
  public boolean judgePoint24(int[] nums) {
      List<Double> list = new ArrayList<Double>();
      for (int num : nums) {
          list.add((double) num);
      }
      return solve(list);
  }
  public boolean solve(List<Double> list) {
      if (list.size() == 0) {
          return false;
      }
      if (list.size() == 1) {
          // 两者之差小于10-6次方
          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) {
                  // list2记录剩下的值
                  List<Double> list2 = new ArrayList<Double>();
                  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) { // 除
                          // Math.abs(list.get(j)) < EPSILON 指当前被除数为 0，跳过
                          if (Math.abs(list.get(j)) < EPSILON) {
                              continue;
                          } else {
                              list2.add(list.get(i) / list.get(j));
                          }
                      }
                      // 递归调用
                      if (solve(list2)) {
                          return true;
                      }
                      // 删除最后一个，回溯其他运算
                      list2.remove(list2.size() - 1);
                  }
              }
          }
      }
      return false;
  }
}

时间复杂度 O(1) ：一共有 9216 种可能性，对于每种可能性，各项操作的时间复杂度都是 O(1)，因此总时间复杂度是 O(1)。
空间复杂度 O(1) ：空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 4 个数，所以递归调用的层数最多为 4，存储中间状态的列表最多包含 4 个元素，因此空间复杂度为常数。

算法(leetcode 牛客网)

679. 24 点游戏**

题目链接

题目描述

解题思路

方法一：回溯法