代码随想录-高级篇之回溯算法

回溯

当你举例子，需要不断用到循环时，这时候就要想到回溯，首先应该举例子，画出树形图，

• 递归函数 + for循环
  

• 回溯方法—纯暴力方法

• 模板

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

• 回溯三部曲
  • 递归函数返回值
  • 终止条件
  • 单层递归逻辑

组合问题

组合

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(int n, int k,int startIndex)
    {
        // 终止条件
        if (path.size() == k)
        {
            res.push_back(path);
            return;
        }
        //单层递归逻辑
        for (int i = startIndex; i <= n; i++)
        {
            path.push_back(i);
            backtracing(n,k,i+1);
            //这里是递归逻辑，
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        // 返回1-n之间，k个说的组合
        backtracing(n,k,1);
        return res;
    }
};

组合总和III

错误版本

/* 找出总和为n的k个数的组合，且这k个数只能是1~9，且每个数只能出现一次
        */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(int n, int k, int startIndex,int curSum)
    {
        // 终止条件
        if (path.size() == k && curSum==n)  // 注意这里不能用&&，两个满足其一就应该结束递归了
        {
            res.push_back(path);
            return;
        }
        //单层递归逻辑
        for (int i = startIndex; i <= 9; i++)
        {
            path.push_back(i);
            curSum += i;
            if (curSum <= n)
            {
                backtracing(n, k, i + 1, curSum);
                path.pop_back();   // 这里回溯了
                //curSum  也应该回溯
            }
            else {
                return;
            }
        }
    }
    //vector<vector<int>> combinationSum3(int k, int n) 
    vector<vector<int>> combinationSum3(int k, int n) {
        // 找出总和为n的k个数的组合，且这k个数只能是1~9，且每个数只能出现一次
        backtracing(n, k, 1,0);
        return res;
    }
};

正确版本

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtracing(int n, int k, int startIndex, int curSum) {
        // 终止条件：终止条件有两个，但是这个两个条件不是&&
        if (path.size() == k) {
            if (curSum == n) 
                res.push_back(path);
            return;
        }

        // 单层递归逻辑
        for (int i = startIndex; i <= 9; i++) {
            path.push_back(i);
            curSum += i;

            backtracing(n, k, i + 1, curSum);

            // 回溯
            path.pop_back();
            curSum -= i; // 注意这里也应该回溯
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        res.clear();
        path.clear();
        backtracing(n, k, 1, 0);
        return res;
    }
};

求电话号码的字母组合

#include<vector>
#include<iostream>
#include<string>

using namespace std;

class Solution {
public:
    string letterMap[10] = {
        "","","abc","def","ghi","jki","mno","pqrs","tuv","wxyz"
    };
    vector<string> res;
    string path;
    void backtracing(string digits, int index)
    {
        if (digits.size() == index)  // 将数字对于的字符串遍历完
        {
            res.push_back(path);
            return;
        }
        int number = digits[index] - '0'; // 取出对应的数字，char的数字-‘0’，转为int类型的数字
        string letter = letterMap[number]; // 取出对应的数字
        for (int i = 0; i < letter.size(); i++)
        {
            path.push_back(letter[i]);      
            backtracing(digits, index + 1); // 递归递归添加下一个数字。
            path.pop_back();
        }
    }
    // 电话号码的字母组合
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return res;
        }
        backtracing(digits, 0);
        // 返回所有的电话号码的字母组合
        return res;
    }
};

组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int>& candidates, int target, int curSum,int index)
    {
        if (curSum == target)
        {
            result.push_back(path);
            return;
        }else if (curSum > target)
            return;

        for ( ; index < candidates.size();)
        {
            curSum += candidates[index];
            path.push_back(candidates[index]);
            backtracing(candidates, target, curSum,index);
            path.pop_back();
            curSum -= candidates[index];
             index++;

        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracing(candidates,target,0,0);

        return result;
    }
};

标准

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int>& candidates, int target, int curSum,int index)
    {
        if (curSum == target)
        {
            result.push_back(path);
            return;
        }else if (curSum > target)
            return;

        for ( int i = index; index < candidates.size(); i++)
        {
            curSum += candidates[i];
            path.push_back(candidates[i]);
            backtracing(candidates, target, curSum, i);
            path.pop_back();
            curSum -= candidates[i];
             index++;
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracing(candidates,target,0,0);

        return result;
    }
};

组合总和II

与组合总和III的区别：组合总和III是从1~9中选择，候选数组中本身没有相同的数字，但是组合总和II有相同的数字

结果去重

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    /*
        思路：想按照组合问题III的走，然后再加入是剔除掉相同的组合即可
    */
    void backtracking(vector<int>& candidates, int target, int curSum, int startIndex) {
        if (curSum == target) {
            // 在这里对 path 进行排序并检查是否存在
            sort(path.begin(), path.end());
            auto it = find(result.begin(), result.end(), path);
            // 注意：返回end表示没有找到
            if (it == result.end()) {  // 如果没有找到相同的 path，则添加到 result 中
                result.push_back(path);
            }
            return;
        }
        if (curSum > target)
            result;

        for (int i = startIndex; i < candidates.size(); ++i) {
            path.push_back(candidates[i]);
            curSum += candidates[i];
            backtracking(candidates, target, curSum, i + 1);  // 递归调用，传递新的 curSum 和索引
            path.pop_back();  // 回溯
            curSum -= candidates[i];
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // 对输入数组进行排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

过程中去重

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    /*
        思路：想按照组合问题III的走，然后再加入是剔除掉相同的组合即可
    */
    void backtracking(vector<int>& candidates, int target, int curSum, int startIndex,int used[]) {
        if (curSum > target)
            return;
        if (curSum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); ++i) {
            if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == 0)
                continue;
            path.push_back(candidates[i]);
            used[i] = 1;
            curSum += candidates[i];
            backtracking(candidates, target, curSum, i + 1,used);  // 递归调用，传递新的 curSum 和索引
            path.pop_back();  // 回溯
            curSum -= candidates[i];
            used[i] = 0;
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // 对输入数组进行排序
        int* used = new int[candidates.size()];
        backtracking(candidates, target, 0, 0,used);
        return result;
    }
};

切割问题

分割回文串

复原IP地址

直接思路

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> res;
    string path;
    int count = 0;
    vector<string> restoreIpAddresses(string s) {
      
        backtracking(s, 0);
        return res;
    }

private:
    void backtracking(const string& s, int start) {
        // 如果已经找到了4段(IP地址应该由4段组成)，并且遍历完了整个字符串，则添加到结果中
        if (count == 4 && start == s.size()) { // 当四个数字都加入的时候才会进入此
            path.erase(path.end() - 1); // 移除最后一个多余的点
            res.push_back(path);
            path += '.';            // 恢复path状态  ？？？？？？？
            return;
        }
        // 如果还没有遍历完字符串，但是已经分了4段，提前返回
        if (count == 4) return;

        for (int i = start; i < s.size() && i < start + 3; ++i) { // 最多取3个字符
            string segment = s.substr(start, i - start + 1);
            int num = stoi(segment);

            // 判断数字是否在0-255之间，并且处理前导0的情况
            if (num <= 255 && (segment == "0" || segment[0] != '0')) {
                // 追加当前段到路径
                path += segment + '.'; // 这里没事，当为path为四个的时候去除最后的小数点就ok了
                count++;
                backtracking(s, i + 1);
                count--;
                // 回溯，移除最后添加的段
                path.erase(path.length() - segment.length() - 1);
            }
        }
    }
};

通过计数点的数量

#include <vector>
#include <string>
using namespace std;

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1, '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            }
            else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

子集问题

子集

• 与组合问题的区别，收获结果时是从每一个节点中去取。
  

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        if (startIndex >= nums.size()) {
            return;
        }

        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {

        backtracking(nums,0);
        return result;
    }
};

子集II

结果去重

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int>& nums, int startIndex) {
        vector<int> tmp = path;
        sort(path.begin(), path.end());
        if (find(result.begin(), result.end(), path) == result.end())  // 标识没有找到
        {
            result.push_back(path);
        }
        path = tmp;
        if (startIndex >= nums.size()) {
            return;
        }

        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        backtracking(nums,0);
        return result;
    }
};

过程去重

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int>& nums, int startIndex, int used[]) {

        result.push_back(path);
        if (startIndex >= nums.size()) {
            return;
        }

        for (int i = startIndex; i < nums.size(); i++) {
            //树层去重：前后两个原始相等，而且已经遍历到相等的第二个元素
            if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == 0)
                continue;
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums,i+1, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 注意一定需要排序
        int* used = new int[nums.size()];
        backtracking(nums,0, used);
        return result;
    }
};

非递减子序列

直接的思路

/*
    这里无非就是：子集问题，要求子集内的元素个数>1,子集内元素按从小到大
*/
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int>& nums, int startIndex, int used[]) {

        if (path.size() > 1)
        {
            result.push_back(path);
        }
        if (startIndex >= nums.size()) {
            return;
        }

        for (int i = startIndex; i < nums.size(); i++) {
            //树层去重：前后两个原始相等，而且已经遍历到相等的第二个元素
            if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == 0)
                continue;
            if (!path.empty() && path.back() > nums[i])
                continue;
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums,i+1, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        int* used = new int[nums.size()];
        backtracking(nums,0, used);
        return result;
    }
};

树层去重

// 版本一
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
            // 注意这里不要加return，要取树上的节点
        }
        //有两种情况不要处理 
            // 1、非递增不处理 
             // 2、递增但是会产生重复结果 例如 4、7、7 第一个7要选 第二个7不要选 否则会产生重复结果
            //用数组去重 一个数组在一层中利用 所以在for循环外面定义
        unordered_set<int> uset; // 使用set对本层元素进行去重
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back())
                || uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

排列问题

全排列

class Solution
{
private:
    vector<int> path;
    vector<vector<int>> result;

public:
    void backtracking(vector<int> &nums, vector<int> used)
    {
        if (path.size() == nums.size())
        {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i] == 1)
                continue;
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
    }
};

全排列II

结果去重

class Solution
{
private:
    vector<int> path;
    vector<vector<int>> result;

public:
    void backtracking(vector<int> &nums, vector<int> used)
    {
        if (path.size() == nums.size())
        {
            if (find(result.begin(), result.end(), path) == result.end())
                result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i] == 1)
                continue;
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
        return result;
    }
};

在回溯过程中去重

class Solution
{
private:
    vector<int> path;
    vector<vector<int>> result;

public:
    void backtracking(vector<int> &nums, vector<int> used)
    {
        if (path.size() == nums.size())
        {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if ( i>0 && nums[i] == nums[i - 1]&&used[i-1] == 0) 
            //  树层去重：注意前提是数组已经经过排序了，相同元素相邻.
            //used[i-1] == 0 保证是输层上去重
                continue;
            if (used[i] == 1)  // 保证一个数字不会被重复选择
              continue; 
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
        return result;
    }
};

棋盘问题

N皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> target;
    vector<vector<string>> solveNQueens(int n) {
        target = vector<string>(n, string(n, '.'));
        rb(n, 0);
        return res;
    }

    void rb(int n, int row) {
        if (n == row) {
            res.push_back(target);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isValid(i, row, n)) {
                continue;
            }
            target[i][row] = 'Q';
            rb(n, row + 1);
            target[i][row] = '.';
        }
    }

    bool isValid(int x, int y, int n) {
        for (int i = 0; i < y; i++) {
            if (target[x][i] == 'Q')
                return false;
        }

        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (target[i][j] == 'Q')
                return false;
        }

        for (int i = x + 1, j = y - 1; i <n && j >= 0; i++, j--) {
            if (target[i][j] == 'Q')
                return false;
        }

        return true;
    }
};

解数独问题

class Solution
{
public:
    bool backtracking(vector<vector<char>> &board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '.')
                {
                    for (char k = '1'; k <= '9'; k++)
                    {
                        if (isvalid(board, k, i, j))
                        {
                            board[i][j] = k;
                            if (backtracking(board))
                                return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isvalid(vector<vector<char>> &board, char val, int row, int col)
    {
        for (int i = 0; i < 9; i++)
        {
            if (board[i][col] == val)
                return false;
        }
        for (int j = 0; j < 9; j++)
        {
            if (board[row][j] == val)
                return false;
        }
        int startrow = (row / 3) * 3;
        int startcol = (col / 3) * 3;
        for (int i = startrow; i < startrow + 3; i++)
        {
            for (int j = startcol; j < startcol + 3; j++)
            {
                if (board[i][j] == val)
                    return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>> &board)
    {
        backtracking(board);
    }
};