24点游戏怎么做？回溯法解析！

大家好，我是顺亿。今天我们来聊聊LeetCode上的一个经典问题——24点游戏。这个问题用回溯法来解决，听起来是不是有点复杂？别担心，我会用最简单的方式带你理解它。

什么是24点游戏？

24点游戏是一个数学游戏，给定四个数字和四种运算符（加、减、乘、除），通过加、减、乘、除的运算，使得结果等于24。比如，给定数字1、7、4、5，我们可以通过(5-1)*(7-4)来得到24。

回溯法思路解析

回溯法是一种解决组合问题的算法。对于24点游戏，我们可以这样思考：

• 首先，从四个数字中选出两个数字进行运算，得到一个新的数字。
• 然后，用这个新数字替换原来的两个数字，形成一个新的数组。
• 接着，在新的数组中重复上述步骤，直到数组中只剩下一个数字。
• 如果这个数字等于24，那么我们就找到了一种解法。

具体实现时，我们需要注意以下几点：

• 枚举所有可能的运算符和括号组合。
• 处理分数的情况，避免精度损失。
• 使用递归实现回溯法。

下面是代码示例：

class Solution {
public:
    bool dfs(vector &cards, int depth, vector rest) {
        if (depth == 3) {
            if (fabs(rest[0] - 21) <= 0.0000001) return true;
            return false;
        }

        int len_rest = rest.size();
        for (int i = 0; i < len_rest; i++) {
            for (int j = i; j < len_rest; j++) {
                if (i == j) continue;
                vector temp = rest;
                temp.erase(find(temp.begin(), temp.end(), rest[i]));
                temp.erase(find(temp.begin(), temp.end(), rest[j]));

                // 加法
                vector temp1 = temp;
                double add = rest[i] + rest[j];
                temp1.emplace_back(add);
                if (dfs(cards, depth + 1, temp1)) return true;

                // 减法
                temp1 = temp;
                double subtract = rest[i] - rest[j];
                temp1.emplace_back(subtract);
                if (dfs(cards, depth + 1, temp1)) return true;

                temp1.pop_back();
                temp.emplace_back(-subtract);  // 相反的情况
                if (dfs(cards, depth + 1, temp1)) return true;

                // 除法
                temp1 = temp;
                double devide = rest[i] / rest[j];
                temp1.emplace_back(devide);
                if (dfs(cards, depth + 1, temp1)) return true;

                temp1.pop_back();
                temp1.emplace_back(rest[j] / rest[i]);  // 相反的情况
                if (dfs(cards, depth + 1, temp1)) return true;

                // 乘法
                temp1 = rest;
                double mutiply = rest[i] * rest[j];
                temp1.emplace_back(mutiply);
                if (dfs(cards, depth + 1, temp1)) return true;
            }
        }
        return false;
    }

    bool judgePoint24(vector &cards) {
        return dfs(cards, 0, vector(cards.begin(), cards.end()));
    }
};

通过以上代码，我们可以解决24点游戏问题。需要注意的是，这个问题的解法可能有很多种，代码中只是实现了一种可能的解法。

好了，今天的分享就到这里。如果你对编程有任何疑问，欢迎在评论区留言。我是顺亿，我们下期再见！

想要了解更多编程知识，请关注「趣航编程网」（www.vqhf.com）。