专题：回溯算法专题（完结）

回溯四部曲
1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
2.确定遍历顺序（有返回值接的需要接住）
3.确定结束条件（注意是否存在中途直接return）
4.确定单层循环逻辑

1.组合

class Solution {
    vector<vector<int>>  result;
    vector<int>  path;
    void backtracking(int n,int k,int startindex){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        if(path.size()==k){
            result.push_back(path);
        return;
        }

        for(int i =startindex;i<=n;i++){
            path.push_back(i);
            backtracking(n,k,i+1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
      backtracking(n,k,1);
      return result;
    }
};

当然也有剪枝

for(int i =startindex;i<=n;i++){

剪枝思考过程 当遍历到i的时候 可以发现已经有path.size()个元素了 还缺 k-path.size()个元素 1…n的时候 也就是从后到前至少有 k-path.size()的元素的才行 因此值是 n-(k-path.size())+1

        for(int i =startindex;i<= n-(k-path.size())+1;i++){
            path.push_back(i);
            backtracking(n,k,i+1);
            path.pop_back();
        }

2.组合总和III

class Solution {
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n,int k,int currentsum,int startindex){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        
        // cout<<"startindex:"<<startindex<<"   currentsum:   "<<currentsum<<endl;
        if(path.size()==k){
            if(currentsum == n){
              result.push_back(path);
            }
           return;
        }
       //  下面用了剪枝 原本是 for(int i=startindex;i<=9;i++){
      for(int i=startindex;i<=9-(k-path.size())+1;i++){
        currentsum = i + currentsum;
        path.push_back(i);
        backtracking(n,k,currentsum,i+1);
        path.pop_back();
        currentsum = currentsum - i;
      }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
      backtracking(n,k,0,1);
      return result;
    }
};

3.电话号码的字母组合

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

    unordered_map <char, string>  mymap{
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"},
        };
    void backtracking(string digits,int index){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        if(index ==digits.size()){
          result.push_back(path);
          return;
        }
        string item = mymap[digits[index]];
        for(int i =0;i<item.size();i++){
            char zimu = item[i];
            path.push_back(zimu);
            backtracking(digits, index+1);
            path.pop_back();

        }
    }
    vector<string> letterCombinations(string digits) {
      if(digits=="") return {};
      backtracking(digits, 0);
      return result;
    }
};

4.组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    void backtracking(vector<int>& candidates, int target,int startindex,int currentsum){
        // 剪枝
        if(currentsum>target){
            return;
        }
        if(currentsum == target){
        result.push_back(path);
        return;
        }
        // cout<<"currentsum:"<<currentsum<<" value:"<<candidates[startindex]<<endl;
        for(int i= startindex;i<candidates.size();i++){
            currentsum = currentsum + candidates[i];
            // 这里也可以直接剪枝 效果比上面剪枝要好 因为不用进入递归函数内部
            // if(currentsum>target){
            //     currentsum = currentsum - candidates[i];
            //     continue;
            // }
            path.push_back(candidates[i]);

            backtracking(candidates,target,i,currentsum);

            path.pop_back();
            currentsum = currentsum - candidates[i];
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};

5.组合总和II

方法一：先排序 用uses去重数层

class Solution {
private:
vector<vector<int>> result;
vector<int> path;
// vector<bool> used; // 下面可以直接赋值
void backtracking(vector<int>& candidates, int target,int currentsum,int startindex,vector<bool>& used){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    if(currentsum>=target){
    if(currentsum==target){
        result.push_back(path);
    }
    return;
    }
    // cout<<"currentsum:"<<currentsum<<"  startindex:"<<startindex<<endl;
    for(int i=startindex;i<candidates.size();i++){
    // 树层去重
    if(i-1>=0 &&candidates[i]==candidates[i-1]&&used[i-1]==false){
        continue;
    }
    used[i]=true;
    path.push_back(candidates[i]);
    currentsum=currentsum+candidates[i];
    backtracking(candidates,target,currentsum,i+1,used);
    currentsum=currentsum-candidates[i];
    path.pop_back();
    used[i]=false;
  }
}

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false);
        backtracking(candidates,target,0,0,used);
        return result;
    }
};

方法二：先排序 用startindex去重数层

class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target,int currentsum,int startindex){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    if(currentsum>=target){
    if(currentsum==target){
        result.push_back(path);
    }
    return;
    }
    // cout<<"currentsum:"<<currentsum<<"  startindex:"<<startindex<<endl;
    for(int i=startindex;i<candidates.size();i++){
    // 树层去重
    if(i>startindex &&candidates[i]==candidates[i-1]){
        continue;
    }
    path.push_back(candidates[i]);
    currentsum=currentsum+candidates[i];
    backtracking(candidates,target,currentsum,i+1);
    currentsum=currentsum-candidates[i];
    path.pop_back();
  }
}

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};

方法三：不排序 直接用set查询该数层之前是否使用过

class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target,int currentsum,int startindex){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    if(currentsum>=target){
    if(currentsum==target){
        result.push_back(path);
    }
    return;
    }
    // cout<<"currentsum:"<<currentsum<<"  startindex:"<<startindex<<endl;
    unordered_set<int> myset;
    for(int i=startindex;i<candidates.size();i++){
    if(myset.count(candidates[i])>0){
        continue;
    }
    myset.insert(candidates[i]);
    path.push_back(candidates[i]);
    currentsum=currentsum+candidates[i];
    backtracking(candidates,target,currentsum,i+1);
    currentsum=currentsum-candidates[i];
    path.pop_back();
    // 要特别注意myset不需要回溯 这个是树层的的变量 同意树层需要用这个判断的
    // myset.erase(candidates[i]);
  }
}

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};

6.分割回文串

class Solution {
 

public:
    vector<vector<string>> result;
    vector<string> path;
    bool IsValid(string newstr) {
        int i=0;
        int j = newstr.size()-1;
        while(i<=j) {
            if(newstr[i]!=newstr[j]){
              return false;
            }
            i++;
            j--;
        }
        return true;
    }

    void backtracking(string s, int startindex) {
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        if(startindex == s.size()){
            result.push_back(path);
            return;
        }
      for(int i=startindex;i<s.size();i++){
        string newstr=s.substr(startindex,i-startindex+1);
        if(!IsValid(newstr)){
           continue;
        }
        path.push_back(newstr);

        backtracking(s,i+1);

        path.pop_back();
      }
    }

    vector<vector<string>> partition(string s) {
       backtracking(s,0);
       return result;
    }
};

7.复原IP地址

这里终止条件

    if(doccount >=4){
        if(startindex == s.size() && doccount==4){
            cout<<"path:"<<path<<endl;
            result.push_back(path.substr(0,path.size()-1));
        }
        return;
    }

完整代码

class Solution {

public:
vector<string> result;
// string path; 添加字符串后 还得再次移除 因此不用全局 直接用临时的
bool IsValid(string newstr){
    if(newstr[0]=='0'&&newstr.size()>1){
        return false;
    }
    int intValue = stoi(newstr);
    if(intValue>255){
        return false;
    }
    return true;
}
void backtracking(string s,int startindex,string path,int doccount){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
    if(doccount >=4){
        if(startindex == s.size() && doccount==4){
            cout<<"path:"<<path<<endl;
            result.push_back(path.substr(0,path.size()-1));
        }
        return;
    }

    for(int i=startindex;i<s.size();i++){
        string newstr = s.substr(startindex,i-startindex+1);
        if(!IsValid(newstr)){
            break;
        }
        doccount++;
        //path+(newstr)+"."不会改变本层的值 而用path.append(newstr).append(".");  这种会改变本层path的值 
        backtracking(s,i+1, path+(newstr)+".",doccount);
        doccount--;
    }
}
    vector<string> restoreIpAddresses(string s) {
      backtracking(s,0,"",0);
      return result;
    }
};

8.子集

求子集的时候 注意收获结果的位置是 二叉树中的每个节点位置 并且终止条件可以不写 因为即使不写终止条件也进入不了for的循环中

class Solution {

public:
vector<vector<int>> result;
vector<int> path{};
void backtracking(vector<int>& nums, int startindex){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
    result.push_back(path);
    // 下面这个终止条件在求子集问题中没有必要 因为进入不了for的循环中
    // if(path.size()>=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;
    }
};

9.子集II

有元素存在重复需要树层剪枝 这里使用 先排序然后用used判断进行剪枝

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path{};
    void backtracking(vector<int>& nums,int startindex,vector<int> & used){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    result.push_back(path);
    for(int i=startindex;i<nums.size();i++){
        if(i-1>=0&&nums[i]==nums[i-1]&&used[i-1]==false){
            continue;
        }
        path.push_back(nums[i]);
        used[i]=true;
        backtracking(nums,i+1,used);
        used[i]=false;
        path.pop_back();
    }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int>  used(nums.size(),false);
        backtracking(nums,0,used);
        return result;
    }
};

10.递增子序列

1.这里需要注意树枝去重 并且不能按照题目的意思不能使用排序 因此去重使用set查询是否在同一层去重

        // 树层去重
        if(myset.count(nums[i])>0){
            continue;
        }
        myset.insert(nums[i]);

2如果不满足递增 应该continue .

        if(!path.empty() && path.back()>nums[i]){
          continue;
        }

完整代码

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
void backtracking(vector<int>& nums,int startindex){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    if(path.size()>=2){
      result.push_back(path);
    }
    unordered_set<int> myset{};
    for(int i=startindex;i<nums.size();i++){
        // 树层去重
        if(myset.count(nums[i])>0){
            continue;
        }
        myset.insert(nums[i]);

        if(!path.empty() && path.back()>nums[i]){
          continue;
        }

        path.push_back(nums[i]);
        backtracking(nums,i+1);
        path.pop_back();
    }
}
    vector<vector<int>> findSubsequences(vector<int>& nums) {
      backtracking(nums,0);
      return result;
    }
};

11.全排列

排列问题 不能依靠startindex了 只能靠used看判断是否使用过避免取重复数字了

class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums,vector<bool>& used){
    // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
    // 2.确定遍历顺序（有返回值接的需要接住）
    // 3.确定结束条件（注意是否存在中途直接return）
    // 4.确定单层循环逻辑
    if(path.size()==nums.size()){
        result.push_back(path);
        return;
    }

    for(int i = 0;i<nums.size();i++){
        if(used[i] == true) {
            continue;
        }
        used[i]=true;
        path.push_back(nums[i]);
        backtracking(nums,used);
        path.pop_back();
        used[i]=false;
    }

}
    vector<vector<int>> permute(vector<int>& nums) {
      vector<bool> used(nums.size(),false);
      backtracking(nums, used);
      return result;

    }
};

12.全排列 II

注意这里树层去重和全排列避免取到相同位置的数字 可以直接共用一个used

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,vector<bool>& used){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i =0;i<nums.size();i++){
            if(i-1>=0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            if(used[i]==true){
                continue;
            }
            used[i]=true;
            path.push_back(nums[i]);
            backtracking(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        backtracking(nums, used);
        return result;
    }
};

13.重新安排行程

14.N皇后

这里可以递归内部控制列填的位置 递归透传行（深度）的大小 当行等于棋盘的大小的时候 可以认为 找到了符合条件的棋盘方法 也就是递归结束
注意下vector初始化

        vector<string> temp(n, string(n, '.'));
        chessboard = temp;

完整代码

class Solution {
    vector<vector<string>> result;
    vector<string> chessboard;
    bool IsValid(vector<string> &chessboard, int n,int low,int col){
        // 检查列 也就是列固定 行变化
        for(int i = low;i>=0;i--){
          if(chessboard[i][col] == 'Q'){
            return false;
          }
        }
        // 不用检查行 因为backtracking已经保证行只能有一个

        // 检查斜角45°
        for(int i=low,j=col;i>=0&&j<=n;i--,j++){

          if(chessboard[i][j] == 'Q'){
            return false;
          }
        }

        // 检查斜角135°
        for(int i=low,j=col;i>=0&&j>=0;i--,j--){
          if(chessboard[i][j] == 'Q'){
            return false;
          }
        }

        return true;
    }
    void backtracking( int n,int startlow){
        // 1.确定是否需要返回值(和题目的递归函数函数是否有返回值无关)
        // 2.确定遍历顺序（有返回值接的需要接住）
        // 3.确定结束条件（注意是否存在中途直接return）
        // 4.确定单层循环逻辑
        if(startlow == n){
          result.push_back(chessboard);
          return;
        }
        for(int col=0;col<n;col++){
            if(!IsValid( chessboard,n, startlow, col)){
                continue;
            }
            chessboard[startlow][col] = 'Q';
            backtracking(n,startlow+1);
            chessboard[startlow][col] = '.';
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> temp(n, string(n, '.'));
        chessboard = temp;
        backtracking(n,0);
        return result;

    }
};

15.解数独

注意点 这里题目帮填了一部分 自己也填了一部分 自己填的一部分 一定要检查所在的这整行 以及整列（N皇后是检查自己填的即可 不用检查整列）

bool IsValid(vector<vector<char>> &board,int n,int m,int row,int col,char k){
    // cout<<"row:"<<row<<" col:"<<col<<" k:"<<k<<endl;
    for(int i =  board.size()-1;i>=0;i--){
      if(board[i][col]==k){
        return false;
      }
    }
    for(int j =  board[0].size()-1;j>=0;j--){
      if(board[row][j]==k){
        return false;
      }
    }

    // 九宫格内只能出现一次
    for(int i =  row/3 * 3;i<row/3 * 3+3;i++){
        for(int j =  col/3 * 3;j<col/3 * 3+3;j++){
            if(board[i][j]==k){
            return false;
            }
        }
    }
    return true;
}

完整代码

class Solution {
public:

bool IsValid(vector<vector<char>> &board,int n,int m,int row,int col,char k){
    // cout<<"row:"<<row<<" col:"<<col<<" k:"<<k<<endl;
    for(int i =  board.size()-1;i>=0;i--){
      if(board[i][col]==k){
        return false;
      }
    }
    for(int j =  board[0].size()-1;j>=0;j--){
      if(board[row][j]==k){
        return false;
      }
    }

    // 九宫格内只能出现一次
    for(int i =  row/3 * 3;i<row/3 * 3+3;i++){
        for(int j =  col/3 * 3;j<col/3 * 3+3;j++){
            if(board[i][j]==k){
            return false;
            }
        }
    }
    return true;
}

bool backtracking(vector<vector<char>>& board,int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]!='.'){
                continue;
            }
            for(char k='1';k<='9';k++){
                if(!IsValid(board,n,m,i,j,k)){
                   continue;
                }
                board[i][j]=k;
                if(backtracking(board,n,m)){
                    for(int i =0;i<9;i++){
                        for(int j =0;j<9;j++){
                         cout<<board[i][j];
                        }
                    }
                    return true;
                };
                board[i][j]='.';
            }
            return false;
        }
    }
    return true;

}
    void solveSudoku(vector<vector<char>>& board) {
        int n = board.size();
        int m = board[0].size();
        backtracking(board,n,m);
    }
};