回溯法

本文学习自labuladong的算法小抄

回溯问题，实际上就是一个决策树的遍历过程。需要思考 3 个问题：

1. 路径：也就是已经做出的选择。

2. 选择列表：也就是你当前可以做的选择。

3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

代码方面，回溯算法的框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！

24点游戏

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

示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/24-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

class Solution {
public:
    static constexpr int TARGET=24;
    static constexpr double EPISILON = 1e-6;
    static constexpr int ADD = 0,MULTIPLY = 1,SUBTRACT = 2,DIVIDE = 3; //四则运算
    bool judgePoint24(vector<int>& nums) {
        vector<double> l;
        for(int num:nums)
            l.emplace_back(static_cast<double>(num));
        return solve(l);
    }
    bool solve(vector<double> &l){
        if(l.size()==0)
            return false;
        if(l.size()==1)
            return abs(l[0]-TARGET)<EPISILON;
        int size = l.size();
        for(int i = 0;i<size;i++){
            for(int j = 0;j<size;j++){
                if(i==j)
                    continue;
                vector<double> list2;
                //先把剩下的数字添加到队列中
                for (int k = 0; k < size; k++) {
                    if (k != i && k != j) {
                        list2.emplace_back(l[k]);
                    }
                }
                //添加新增的运算结果
                for(int k = 0;k<4;k++){
                    if(k<2&&i>j)
                        continue;
                    switch(k){
                    case ADD: list2.emplace_back(l[i]+l[j]);break;
                    case MULTIPLY: list2.emplace_back(l[i]*l[j]);break;
                    case SUBTRACT: list2.emplace_back(l[i]-l[j]);break;
                    case DIVIDE: {
                        if(abs(l[j])<EPISILON)
                            continue;
                        list2.emplace_back(l[i]/l[j]);
                        }
                    default: break;
                    }
                    if(solve(list2))
                        return true;
                    list2.pop_back();
                }
            }
        }
        return false;
    }
};

打赏