leetcode：679. 24 点游戏

题目

给定一个长度为 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 。

示例：

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

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

解答 & 代码

递归回溯：遍历 9216 种不同的可能性

1. 从 4 个数中选择两个数，分别进行 加、减、乘、除 4 种运算，将运算结果代替两个数，剩余 3 个数，递归
   1. 选择两个数通过双重循环枚举
2. 从 3 个数中选择两个数，分别进行 加、减、乘、除 4 种运算，将运算结果代替两个数，剩余 2 个数，递归
3. 从 2 个数中选择两个数，分别进行 加、减、乘、除 4 种运算，将运算结果代替两个数，剩余 1 个数，递归
4. 只剩下一个数，递归结束。判断剩下的这个数是否等于 24，如果等于 24 则返回 true，否则返回 false

剪枝：

1. 对当前选择的两个数，当加、减、乘、除有一种情况返回 true 了，就不用递归探索其它情况。做法：
   1. 设置变量 isValid，初始化为 false
   2. 对于每种运算情形，递归调用方式为 isValid = isValid || backTrack(remainNums)，这样当前面已经有一种情形为 true 时，isValid 已经为 true，就不会调用 || 后面的 backTrack 函数
2. 如果运算符号为 加号、乘号，由于交换律，两个数的位置是无所谓的，因此只需要进行一次运算
3. 除法如果除数为 0，则直接跳过

浮点数的比较：

• 递归结束条件是看剩余的数是否等于 24，但由于是浮点数，因此判断相等时要考虑精度，误差小于即可认为相等

• 判定除数是否为 0 时，也是看其绝对值是否小于

  class Solution {
  private:
    int target = 24;
    double epsilon = 1e-6;
  
    // 递归回溯
    bool backTrack(vector<double> nums)
    {
        int len = nums.size();
        // 递归结束条件：只剩下一个数时直接返回
        // 如果 nums[0] == target，则返回 true，否则返回 false
        // 通过 abs(nums[0] - target) < epsilon 来判断 nums[0] 是否等于 target
        if(len == 1)
            return abs(nums[0] - target) < epsilon;
  
        // 对于当前的 len 个数字，从中任意取两个数字，对这两个数字进行四种可能的运算，
        // 再用运算结果代替这两个数，剩余的数继续递归处理。
        // 两层循环，枚举所有可能的两个数
        for(int i = 0; i < len; ++i)
        {
            for(int j = i + 1; j < len; ++j)
            {
                // 1. 选择两个数
                double num1 = nums[i];        // 选择的第一个数
                double num2 = nums[j];        // 选择的第二个数
                vector<double> remainNums;    // 数组中剩余的数
                for(int k = 0; k < len; ++k)
                {
                    if(k != i && k != j)
                        remainNums.push_back(nums[k]);
                }
  
                // 2. 进行四种可能的操作，每种操作都可以交换两个数，但加法、乘法有交换律
                bool isValid = false;
                // 2.1 加法
                remainNums.push_back(num1 + num2);
                isValid = isValid || backTrack(remainNums);
                remainNums.pop_back();
                // 2.2 减法（两个数顺序不同对应两种结果）
                remainNums.push_back(num1 - num2);
                isValid = isValid || backTrack(remainNums);
                remainNums.pop_back();
                remainNums.push_back(num2 - num1);
                isValid = isValid || backTrack(remainNums);
                remainNums.pop_back();
                // 2.3 乘法
                remainNums.push_back(num1 * num2);
                isValid = isValid || backTrack(remainNums);
                remainNums.pop_back();
                // 2.4 除法（两个数顺序不同对应两种结果）
                // 直接跳过除数为 0 的情况（abs(num) <= 1e-6 则认定为 0）
                if(abs(num2) > 1e-6)
                {
                    remainNums.push_back(num1 / num2);
                    isValid = isValid || backTrack(remainNums);
                    remainNums.pop_back();
                }
                if(abs(num1) > 1e-6)
                {
                    remainNums.push_back(num2 / num1);
                    isValid = isValid || backTrack(remainNums);
                    remainNums.pop_back();
                }
  
                // 如果存在一种情况为 true，则直接返回 true
                if(isValid)
                    return true;
            }
        }
        // 遍历结束，如果都没有为 true 的情况，则返回 false
        return false;
    }
  public:
    bool judgePoint24(vector<int>& cards) {
        int len = 4;
        vector<double> nums(4);
        for(int i = 0; i < len; ++i)
            nums[i] = double(cards[i]);
  
        return backTrack(nums);
    }
  };
  

  复杂度分析：

• 时间复杂度 O(1)：一共要遍历 9216 种可能性，对于每种可能性的处理时间 O(1)

  • 一共有 4 个数和 3 个运算操作（4 种可选运算操作）
    1. 从 4 个数中选有序的两个数，共 4*3 = 12 种可能，有 4 种运算操作，共 48 种可能。操作完后两个数的结果代替两个数，剩余 3 个数
    2. 从 3 个数中选有序的两个数，共 3*2 = 6 种可能，有 4 种运算操作，共 24 种可能。操作完后两个数的结果代替两个数，剩余 2 个数
    3. 从 2 个数中选有序的两个数，共 2*1 = 2 种可能，有 4 种运算操作，共 8 种可能。
    4. 48248 = 9216 种可能
• 空间复杂度 O(1)：递归最大深度为 4

执行结果：

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了 34.38% 的用户
内存消耗：14.6 MB, 在所有 C++ 提交中击败了 24.84% 的用户