回溯算法

回溯算法

回溯算法是暴力算法的一种，实际效率并不高，只是一种没有办法的办法

1 解题步骤

回溯算法可以说就是递归 + for 循环，大多都可以抽象成树的形式，在上一章的基础上构建 for 循环

解决的都是在集合中递归查找⼦集，集合的⼤⼩就构成了树的宽度，递归的深度，构成的树的深度。

回溯算法三部曲：

1. 回溯的返回一般都是 void，⼀般是先写逻辑，然后需要什么参数，就填什么参数
2. 终止条件，一般是找到一个符合条件的数值的时候
3. 遍历过程：横向外层 for 遍历宽度，纵向递归遍历深度

void backtracking(参数) {
    if (终⽌条件) {
    存放结果;
    return;
    }
for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

2 题目选取

2.1 组合总和 II

带去重的组合，需要理解组合的本质

同一层上，不允许取两个相同的数：因为不同 case 取同一个数，本质没有区别

在深度上，允许取两个相同的数字：因为同一个 case 内，同个数字取值本质上有区别

注意：树层的去重，需要进行排序

class Solution {
/*
 横向不允许相同数字，去重需要排序
 纵向允许相同数字，用 start 实现
*/
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        ret.clear();
        sort(candidates.begin(), candidates.end());
        traceback(0, candidates, target);
        return ret;
    }
    vector<bool> used;
    vector<int> path;
    vector<vector<int>> ret;
    void traceback(int start, const vector<int>& candidates, int remain) {
        if (remain < 0) return;
        if (remain == 0) {
            ret.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); i++) {
            // 注意这里的去重逻辑，要和 start 比较
            if (i > start && candidates[i - 1] == candidates[i]) {
                // 表示存在上一个数字, 且相等，横向跳过，不可以修改循环边界 start
                continue;
            }
            // 数组排序剪枝
            if (candidates[i] > remain) break;
            remain -= candidates[i];
            path.push_back(candidates[i]);
            // 纵向，使用 used 去重？
            traceback(i + 1, candidates, remain);
            remain += candidates[i];
            path.pop_back();
        }
    }
};

2.2 分割字符串类（回文串）

这类问题主要关注 不同的 path 定义，以及循环的条件

实际上就是放隔板问题，但是要考虑好隔板怎么能够在代码中实现

这里使用思路：左闭右开区间，左有两个索引固定，在循环开始时候分割，重点位置在注释中标出

class Solution {
public:
    vector<vector<string>> partition(string s) {
        auto curr = s.begin();
        traceback(s, curr);
        return ret;
    }
    vector<vector<string>> ret;
    vector<string> path;
    void traceback(const string& s, string::iterator curr) {
        if ((curr - s.begin()) >= s.size()) {
            // 数量满足，终止条件
            ret.push_back(path);
            return;
        }
        // 这里的 for 循环已经实现了 + 1 逻辑，外层不能 + 1
        // 左闭右开区间，+ 1 代表仅纳入了一个字符
        for (auto i = curr + 1; i <= s.end(); i++) {
            if (is_palindrome(curr, i)) {
                // 是回文，加入并递归，（也就是先判断再加入组合 path）
                path.push_back(string(curr, i));
                traceback(s, i);    // 左闭右开， + 1 逻辑在 for 循环实现
                path.pop_back();
            } else {
                continue;
            }
        }
    }
    bool is_palindrome(string::iterator first, string::iterator last) {
        if (first == last) return true;   // 空串
        --last; // 右开变右闭
        while (first < last) {
            if (*first != *last)
                return false;
            ++first;
            --last;
        }
        return true;
    }
};

2.3 非递减子序列

本题是横向去重的典型例子

主要在于如何进行层内去重，重点是掌握层内的作用区间：for 循环内，调用递归值之前

#include <vector>
#include <unordered_set>

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        ret.clear();
        path.clear();
        backtrack(0, INT_MIN, nums);
        return ret;
    }

    vector<vector<int>> ret;
    vector<int> path;

    void backtrack(int start, int pre, vector<int>& nums) {
        // pre 代表上一数字
        if (path.size() > 1) {
            ret.push_back(path);
        }
        int i = start;
        unordered_set<int> used; // 递归层内变量
        for (int i = start; i < nums.size(); i++) {
            // 本层内去重
            if (used.count(nums[i])) continue;
            if (pre > nums[i]) continue;

            used.insert(nums[i]);
            path.push_back(nums[i]);
            backtrack(i + 1, nums[i], nums);
            path.pop_back();
        }
    }
};

2.4 全排列去重

非常独特的一个横纵结合的去重逻辑

排列不可以使用 startIndex，因为要遍历所有的节点

纵向不可以使用用过的下标值

横向去重需要考虑纵向是否使用过该数值，使用过则解禁，没用过则需要去重

注意条件满足需要返回，因为需要在叶子节点切断递归

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        ret.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        traceback(used, nums);
        return ret;
    }

    vector<vector<int>> ret;
    vector<int> path;
    // 纵向不可以使用相同元素
    // 横向去除同数值但下标不同元素
    void traceback(vector<bool>& used, const vector<int>& nums) {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return; // 这里要切断递归，是终止条件
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                // 指的是纵向没有使用过，并且横向数值相同（所以要排序）
                // 纵向使用过就可以再次使用了
                continue;
            }
            if (used[i]) continue; // 纵向去重

            int curr = nums[i];
            path.push_back(curr);
            used[i] = true;
            traceback(used, nums);

            used[i] = false;
            path.pop_back();
        }
    }
};

3 总结

3.1 什么时候需要 startIndex？

需要横向去重的时候，有时候会配合排序来执行数值去重

3.2 纵向横向去重分别怎么实现？

3.2.1 纵向

纵向去重，使用 bool 类型 used 标记即可，注意 used 是全局变量

vector<bool> used; // 需要初始化为全 fasle
void backtrace() {
    if (...) {}
    for (int i = 0; i < value.size(); i++) {
    if (used[i]) continue;
        used[i] = true;
        backtrace(); // 使用 used 包裹，回溯退出需要回退状态
        used[i] = false;
    }
}

3.2.2 横向

1. 没有重复元素，在递归时候传递 startIndex + 1 即可

void backtrace(int startIndex) {
    if (...) {}
    for (int i = startIndex; i < end; i++) {
        ...;
        backtrace(startIndex + 1);
        ...;
    }
}

2. 有重复元素，可以排序后额外判断与上一个是否相等

sort(value.begin(), value.end());
void backtrace(int startIndex) {
    if (...) {}
    for (int i = startIndex; i < value.size(); i++) {
        if (i > 0 && value[i] == value[i - 1]) continue; // 去重
        ...;
        backtrace(startIndex + 1);
    }
}

3.3 返回值

3.3.1 什么时候 return

return 的唯一逻辑是：

1. 无路可走
2. 这条节点已经失败了

3.3.2 不同位置的 return

1. if终止条件：

• 需要继续搜索 → return（存答案以后继续兄弟分支）

• 不需要继续搜索 → return true（直接停止整个搜索）

2. for 循环内部：

• 当前分支无效但下一分支还有希望 → continue

• 当前分支无效且后续分支也无希望 → return（剪枝）

如果需要获取所有节点，可以在 if 下写 return 而是通过 for 的逻辑进行控制

3.3.3 返回值设置

绝大多数情况都是 void

除非找到一种情况立刻返回，此时使用 bool，同时递归写法也会改变

if (traceback(...)) return true;