More content：力扣题记之回溯

回溯是递归的副产物，只要有递归就会有回溯

回溯算法模板：回溯递归是往深处找，内部for遍历是横向找

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

其中，回溯有以下两种方式：

①明确修改值，再撤销修改

path.push_back(i);
sum -= i;
depth++;
backTracking(sum, depth);
sum += i;
depth--;
path.pop_back()

②以传递参数的形式修改，递归函数内使用的是新的变量值，外部变量值未被修改，相当于回溯了

path.push_back(i);
backTracking(sum - i, depth + 1); //注意depth+1一定不要写成depth++，不然值就改变了
path.pop_back()

回溯算法可解决的问题类型：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

---

46. 全排列✅

用一个数组来记录nums下标的状态，即记录下标对应的元素是否被用过(比如flags[2] = 1代表nums[2]被使用过了)

ps：为什么不直接记录元素是否被用过？因为元素中有负数，下标都是非负数，所以用下标来记录下标，反正nums数组的下标和元素对应关系不会变

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> flags;
public:
    void backTracking(vector<int>& nums) {
        if(path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i++) {
            if(flags[i]) continue;
            path.push_back(nums[i]);
            flags[i] = 1;
            backTracking(nums);
            path.pop_back();
            flags[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        flags.resize(nums.size(), 0);
        backTracking(nums);
        
        return res;
    }
};

---

78. 子集✅

控制一下长度即可

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

public:
    void backTracking(vector<int>& nums, int startIndex, int len) {
        if(path.size() == len) {
            res.push_back(path);
            return ;
        }

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

        for(int i = 1; i < nums.size(); i++) {
            backTracking(nums, 0, i);
        }

        return res;
    }
};

---

17. 电话号码的字母组合✅

定义全局变量，精简递归函数参数

class Solution {
private:
    vector<string> res;
    string path;
    int n;
    unordered_map<char, string> mp;
public:
    void backtracking(string digits, int depth) {
        if(path.size() == n) {
            res.push_back(path);
            return ;
        }

        for(const char &i : mp[digits[depth]]) {
            path += i;
            backtracking(digits, depth + 1);
            path.erase(path.size() - 1, 1);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(!digits.size()) return res;
        
        mp['2'] = "abc";
        mp['3'] = "def";
        mp['4'] = "ghi";
        mp['5'] = "jkl";
        mp['6'] = "mno";
        mp['7'] = "pqrs";
        mp['8'] = "tuv";
        mp['9'] = "wxyz";

        n = digits.size();
        backtracking(digits, 0);

        return res;
    }
};

---

39. 组合总和✅

target递减，由两个参数变为一个参数

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backtracking(vector<int>& candidates, int sub_target, int startIndex) {
        if(sub_target < 0) return ; //和超出目标了，作废
        if(!sub_target) { //和正好等于目标值，记录
            res.push_back(path);
            return ;
        }

        for(int i = startIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            backtracking(candidates, sub_target - candidates[i], i); //允许重复选取当前元素，但不能回到之前的元素
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0);

        return res;
    }
};

---

22. 括号生成✅

一个字符一个字符地递归着往后搜，每个字符只有两种可能性

先搜出来再检测合法性

class Solution {
private:
    vector<string> res;
    string path = "("; //第一个字符必是左括号
public:
    void backTracking(int n) {
        if(path.size() == n * 2) {
            if(checkValid(path)) res.push_back(path);
            return ;
        }

        path += '(';
        backTracking(n);
        path.erase(path.size() - 1, 1);

        path += ')';
        backTracking(n);
        path.erase(path.size() - 1, 1);
    }

    bool checkValid(string s) { 
        stack<char> sk;
        for(const char &c : s) {
            if(c == ')' && !sk.empty() && sk.top() == '(') sk.pop();
            else sk.push(c);
        }
        if(sk.empty()) return true;
        return false;
    }

    vector<string> generateParenthesis(int n) {
        backTracking(n);
        return res;
    }
};

---

79. 单词搜索✅

一个格子一个格子地递归回溯着搜，遍历四个方向

不用存储答案，遇到直接返回，因此递归函数返回值为bool

class Solution {
private:
    int m, n; //m行n列
public:
    bool backTracking(vector<vector<char>>& board, vector<vector<bool>> &used, string word, int row, int col, int index) {
        if(index == word.size()) return true;

        //遍历四个方向
        if(row != 0 && board[row - 1][col] == word[index] && !used[row - 1][col]) { //上
            used[row - 1][col] = true;
            if(backTracking(board, used, word, row - 1, col, index + 1)) return true; //一旦搜到答案，立刻返回 
            used[row - 1][col] = false;
        }
        if(row != m - 1 && board[row + 1][col] == word[index] && !used[row + 1][col]) { //下
            used[row + 1][col] = true;
            if(backTracking(board, used, word, row + 1, col, index + 1)) return true; //一旦搜到答案，立刻返回 
            used[row + 1][col] = false;
        }
        if(col != 0 && board[row][col - 1] == word[index] && !used[row][col - 1]) { //左
            used[row][col - 1] = true;
            if(backTracking(board, used, word, row, col - 1, index + 1)) return true; //一旦搜到答案，立刻返回 
            used[row][col - 1] = false;
        }
        if(col != n - 1 && board[row][col + 1] == word[index] && !used[row][col + 1]) { //右
            used[row][col + 1] = true;
            if(backTracking(board, used, word, row, col + 1, index + 1)) return true; //一旦搜到答案，立刻返回 
            used[row][col + 1] = false;
        }

        return false; //四个方向都搜寻无果，返回false                    
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();

        vector<vector<bool>> used(m, vector<bool>(n, false)); //初始化标记数组

        //搜到首字母进入递归
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == word[0]) {
                    used[i][j] = true;
                    if(backTracking(board, used, word, i, j, 1)) return true;
                    used[i][j] = false; //虽然这个首字母没走到最后，但可能别人还需要它
                }
            }
        }

        return false;

    }
};

---

131. 分割回文串✅

与93. 复原 IP 地址思路一样(遍历回溯切割 + 检测非法字段) 但更简单一些

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
public:
    void backTracking(string s, int startIndex) {
        if(s.size() == startIndex) {
            res.push_back(path);
            return ;
        }
  
        for(int i = 1; startIndex + i <= s.size(); i++) { //遍历要切的位数    
            if(!checkPalindrome(s, startIndex, i)) continue;
            path.push_back(s.substr(startIndex, i));
            backTracking(s, startIndex + i);
            path.pop_back();
        }
    }

    bool checkPalindrome(string s, int beginIndex, int len) {
        int l = beginIndex;
        int r = beginIndex + len - 1;
        while(l <= r) {
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        // if(checkPalindrome(s, 0, 3)) cout << "yes";
        // else cout << "no";
        return res;
    }
};

---

51. N 皇后❌

思路没问题，先按行搜出所有方案，再对列、撇、捺进行合法性检查，但没想出撇和捺的检查公式，缺点是搜出所有方案在筛选，效率低

在搜的过程中就检查合法性，非法的直接跳过

class Solution {
private:
    vector<vector<string>> res;
public:
    void backTracking(vector<string> &tep, int n, int row) {
        if(row == n) {
            res.push_back(tep); 
            return ;
        }

        for(int col = 0; col < n; col++) { //只遍历当前行的每列，遍历行递归实现
            if(checkValid(row, col, tep, n)) { 
                tep[row][col] = 'Q';
                backTracking(tep, n, row + 1); //row相当于深度
                tep[row][col] = '.'; //回溯,撤销Q
            }
        }
    }

    bool checkValid(int row, int col, vector<string> &tep, int n) {
        for(int i = 0; i < n; i++) { //检查列
            if(tep[i][col] == 'Q') return false;
        }
      
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { //检查捺
            if(tep[i][j] == 'Q') {
                return false;
            }
        }

        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { //检查撇
            if(tep[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> tep(n, string(n, '.')); //初始化棋盘，等效于下面数行
        // vector<string> tep;
        // for(int i = 0; i < n; i++) {
        //     string s;
        //     for(int j = 0; j < n; j++) {
        //         s += '.';
        //     }
        //     tep.push_back(s);
        // }
        backTracking(tep, n, 0);
        
        return res;
    }
};