1. 46. 全排列

  1. class Solution {
  2. public:    
  3.     vector<vector<int>> result;  //存放符合条件结果的集合
  4.     vector<int> path;  //存放符合条件的结果
  5.     vector<vector<int>> permute(vector<int>& nums) {  
  6.         vector<bool> used(nums.size(),false);
  7.         backtracking(nums,used);   
  8.         return result;
  9.     }
  10.     void backtracking(vector<int>& nums,vector<bool>& used){
  11.         //终止条件
  12.         if(path.size()==nums.size()){
  13.             result.push_back(path);
  14.             return;
  15.         }
  16.         //遍历
  17.         for(int i=0;i<nums.size();i++){
  18.             //做选择
  19.             if(used[i]){
  20.                 continue;
  21.             }
  22.             used[i]=true;
  23.             path.push_back(nums[i]);
  24.             //递归
  25.             backtracking(nums,used);
  26.             //撤销选择
  27.             path.pop_back();
  28.             used[i]=false;
  29.         }
  30.     }
  31. };

2. 77. 组合

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(int n,int k,int startIndex){
  6.         //终止条件
  7.         if(path.size()==k){
  8.             result.push_back(path);
  9.             return ;
  10.         }
  11.         //遍历
  12.         //-----------优化：for(int i=startIndex;i<=n-k+path.size()+1;i++)------------//
  13.         for(int i=startIndex;i<=n;i++){
  14.             //选择，处理节点
  15.             path.push_back(i);
  16.             //递归
  17.             backtracking(n,k,i+1);
  18.             //回溯，撤销处理的节点
  19.             path.pop_back();
  20.         }
  21.     }
  22.     vector<vector<int>> combine(int n, int k) {
  23.         backtracking(n,k,1);
  24.         return result;
  25.     }
  26. };

3. 216. 组合总和 III

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(int targetSum,int k,int sum,int startIndex){ 
  6.         //终止条件       
  7.         if(path.size()==k){
  8.             if(sum==targetSum){
  9.                 result.push_back(path);
  10.                 return;
  11.             }
  12.         }
  13.         //遍历
  14.         for(int i=startIndex;i<=9;i++){
  15.             //选择
  16.             sum+=i;
  17.             path.push_back(i);
  18.             //递归
  19.             backtracking(targetSum,k,sum,i+1);
  20.             //回溯，撤销选择
  21.             sum-=i;
  22.             path.pop_back();
  23.         }
  24.     }
  25.     vector<vector<int>> combinationSum3(int k, int n) {
  26.         backtracking(n,k,0,1);
  27.         return result;
  28.     }
  29. };
  32. //剪枝优化
  33. class Solution {
  34. public:
  35.     vector<vector<int>> result;
  36.     vector<int> path;
  37.     void backtracking(int targetSum,int k,int sum,int startIndex){ 
  38.         //终止条件   
  39.         if(sum>targetSum){
  40.             return;
  41.         }    
  42.         if(path.size()==k){
  43.             if(sum==targetSum){
  44.                 result.push_back(path);
  45.                 return;
  46.             }
  47.         }
  48.         //遍历             
  49.         for(int i=startIndex;i<=10-k+path.size();i++){
  50.             //选择
  51.             sum+=i;
  52.             path.push_back(i);
  53.             //递归
  54.             backtracking(targetSum,k,sum,i+1);
  55.             //回溯，撤销选择
  56.             sum-=i;
  57.             path.pop_back();
  58.         }
  59.     }
  60.     vector<vector<int>> combinationSum3(int k, int n) {
  61.         backtracking(n,k,0,1);
  62.         return result;
  63.     }
  64. };

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

  1. class Solution {
  2. private:
  3.     //映射
  4.     const string letterMap[10]={
  5.         "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
  6.     };
  7. public:
  8.     vector<string> result;
  9.     string path;
  10.     void bakctracking(const string& digits,int index){
  11.         //终止条件,digits里边遍历完就结束
  12.         if(digits.size()==index){
  13.             result.push_back(path);
  14.             return;
  15.         }
  16.         int digit=digits[index]-'0';
  17.         string letter=letterMap[digit];
  18.         //遍历：选择——递归——撤销选择（回溯）
  19.         for(int i=0;i<letter.size();i++){
  20.             path.push_back(letter[i]);
  21.             bakctracking(digits,index+1);
  22.             path.pop_back();
  23.         }
  24.     }
  25.     vector<string> letterCombinations(string digits) {
  26.         if(digits.size()==0){
  27.             return result;
  28.         }
  29.         bakctracking(digits,0);
  30.         return result;
  31.     }
  32. };

5. 39. 组合总和

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& candidates, int target,int sum,int startIndex){
  6.         //终止条件
  7.         if(sum>target){
  8.             return ;
  9.         }
  10.         if(target==sum){
  11.             result.push_back(path);
  12.             return;
  13.         }
  14.         //遍历：选择——递归——撤销选择（回溯）
  15.         for(int i=startIndex;i<candidates.size();i++){
  16.             sum+=candidates[i];
  17.             path.push_back(candidates[i]);
  18.             backtracking(candidates,target,sum,i);
  19.             sum-=candidates[i];
  20.             path.pop_back();
  21.         }
  22.     }
  23.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  24.         backtracking(candidates,target,0,0);
  25.         return result;
  26.     }
  27. };
  29. ///
  30. class Solution {
  31. public:
  32.     vector<vector<int>> result;
  33.     vector<int> path;
  34.     void backtracking(vector<int>& candidates, int target,int sum,int startIndex){
  35.         //终止条件
  36.         if(sum>target){
  37.             return ;
  38.         }
  39.         if(target==sum){
  40.             result.push_back(path);
  41.             return;
  42.         }
  43.         //遍历：选择——递归——撤销选择（回溯）
  44.         //优化点：sum>target就没有必要继续递归了
  45.         for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
  46.             sum+=candidates[i];
  47.             path.push_back(candidates[i]);
  48.             backtracking(candidates,target,sum,i);
  49.             sum-=candidates[i];
  50.             path.pop_back();
  51.         }
  52.     }
  53.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  54.         //剪枝优化需要排序
  55.         sort(candidates.begin(),candidates.end());
  56.         backtracking(candidates,target,0,0);
  57.         return result;
  58.     }
  59. };

6. 40. 组合总和 II

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& candidates, int target,int sum,int startIndex,vector<bool> used){
  6.         //终止条件
  7.         if(sum>target){
  8.             return;
  9.         }
  10.         if(sum==target){
  11.             result.push_back(path);
  12.             return ;
  13.         }
  14.         //遍历：选择——递归——撤销选择
  15.         for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
  16.             //去重，对同一层上已经使用过的元素进行跳过
  17.             //used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  18.             //used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  19.             if(i>0&&candidates[i-1]==candidates[i]&&used[i-1]==false){
  20.                 continue;
  21.             }
  22.             sum+=candidates[i];
  23.             used[i]=true;
  24.             path.push_back(candidates[i]);
  25.             backtracking(candidates,target,sum,i+1,used);
  26.             sum-=candidates[i];
  27.             used[i]=false;
  28.             path.pop_back();
  29.         }
  30.     }
  31.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  32.         sort(candidates.begin(),candidates.end());
  33.         vector<bool> used(candidates.size(),false);
  34.         backtracking(candidates,target,0,0,used);
  35.         return result;
  36.     }
  37. };

7. 131. 分割回文串

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;    
    void backtracking(const string& s,int startIndex){
        //终止条件
        if(startIndex>=s.size()){
            result.push_back(path);
            return;
        }
        //遍历：选择——递归——撤销选择
        for(int i=startIndex;i<s.size();i++){
            //选择：判断是否是回文
            if(isPalindrome(s,startIndex,i)){
                string str=s.substr(startIndex,i+1-startIndex);
                path.push_back(str);
            }else{
                continue;
            }
            backtracking(s,i+1);
            path.pop_back();
        }
    }
    //双指针判断是否是回文
    bool isPalindrome(const string& s,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            if(s[i]!=s[j]){
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return result;
    }
};

8. 93. 复原 IP 地址

class Solution {
public:
    vector<string> result;
    void backtracking(string& s,int startIndex,int pointNum){
        if(pointNum==3){    //已经分割好了，判断第四段是否合法
            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)){
                s.insert(s.begin()+i+1,'.');
                pointNum++; 
                //递归时多了一个. 所以i+2
                backtracking(s,i+2,pointNum);
                pointNum--;
                s.erase(s.begin()+i+1);
            }else{
                break;
            }
        }
    }
    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++){    //大于255不合法
            if(s[i]>'9'||s[i]<'0'){
                return false;
            }
            num=num*10+(s[i]-'0');
            if(num>255){
                return false;
            }
        }
        return true;
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.size()>12){
            return result;
        }
        backtracking(s,0,0);
        return result;
    }
};

9. 78. 子集

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;
    }
};

10. 90. 子集 II

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex,vector<bool> used){
        //终止条件，注意包含自身
        result.push_back(path);
        if(startIndex>=nums.size()){
            return;
        }
        //遍历：选择——递归——撤销选择，注意去重
        for(int i=startIndex;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,i+1,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {  
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);      
        backtracking(nums,0,used);
        return result;
    }
};

//
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex){
        //终止条件，注意包含自身
        result.push_back(path);
        unordered_set<int> uset;  //在本层中去重
        //遍历：选择——递归——撤销选择，注意去重,用set去重
        for(int i=startIndex;i<nums.size();i++){
            if(uset.find(nums[i])!=uset.end()){
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {  
        sort(nums.begin(),nums.end());     
        backtracking(nums,0);
        return result;
    }
};

11. 491. 递增子序列

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex){
        //终止条件
        if(path.size()>1){
            result.push_back(path);
            //不返回，要取全部节点
        }
        //遍历：选择——递归——取消选择、回溯，注意去重，用set
        unordered_set<int> uset;
        for(int i=startIndex;i<nums.size();i++){
            //去重 非递增或重复时退出本次循环
            if((uset.find(nums[i])!=uset.end())||!path.empty()&&nums[i]<path.back()){
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

12. 47. 全排列 II

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,vector<bool>& 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]==false){
                continue;
            }
            if(used[i]==false){
                used[i]=true;
                path.push_back(nums[i]);
                backtracking(nums,used);
                path.pop_back();
                used[i]=false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtracking(nums,used);
        return result;
    }
};

13. 332. 重新安排行程

class Solution {
public:
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    //航班次数+1、-1 因为有重复
    unordered_map<string,map<string,int>> target;
    int backtracking(int ticketNum,vector<string>& result){
        //终止条件
        if(result.size()==ticketNum+1){
            return true;
        }
        //遍历：选择——递归——撤销选择、回溯
        for(pair<const string,int>& tar:target[result[result.size()-1]]){
            //还能往这个机场飞
            if(tar.second>0){
                result.push_back(tar.first);
                tar.second--;
                if(backtracking(ticketNum,result)){
                    return true;
                }
                result.pop_back();
                tar.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        //机场映射关系 初始化
        for(const vector<string>& vec:tickets){
            target[vec[0]][vec[1]]++;
        }
        result.push_back("JFK");
        backtracking(tickets.size(),result);
        return result;
    }
};

14. 51. N 皇后

class Solution {
public:
    vector<vector<string>> result;
    vector<int> path;
    void backtracking(int n,int row,vector<string>& chessboard){
        //终止条件
        if(n==row){
            result.push_back(chessboard);
            return;
        }
        //遍历：选择——递归——撤销选择、回溯
        for(int col=0;col<n;col++){
            if(isValid(row,col,chessboard,n)){
                chessboard[row][col]='Q';
                backtracking(n,row+1,chessboard);
                chessboard[row][col]='.';
            }
        }
    }
    bool isValid(int row,int col,vector<string>& chessboard,int n){
        //不能同列
        for(int i=0;i<row;i++){
            if(chessboard[i][col]=='Q'){
                return false;
            }
        }
        //检查45度
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chessboard[i][j]=='Q'){
                return false;
            }
        }
        //检查135度
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(chessboard[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));
        backtracking(n,0,chessboard);
        return result;
    }
};

15. 37. 解数独

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]!='.'){
                    continue;
                }
                for(char k='1';k<='9';k++){
                    if(isValid(i,j,k,board)){
                        board[i][j]=k;
                        if(backtracking(board)){
                            return true;
                        }
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(int row,int col,char val,vector<vector<char>>& board){
        //判断行里是否有重复
        for(int i=0;i<board.size();i++){
            if(board[i][col]==val){
                return false;
            }
        }
        //判断列里是否有重复
        for(int j=0;j<board[0].size();j++){
            if(board[row][j]==val){
                return false;
            }
        }
        //判断9宫格是否有重复
        int rowStart=row/3*3;
        int colStart=col/3*3;
        for(int i=rowStart;i<rowStart+3;i++){
            for(int j=colStart;j<colStart+3;j++){
                if(board[i][j]==val){
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

16. 200. 岛屿数量

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int result=0;
        int m=grid.size(),n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    result++;
                    dfs(grid,i,j);
                }
            }
        }
        return result;
    }

    void dfs(vector<vector<char>>& grid,int i,int j){
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n){
            return;
        }
        if(grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';//变为海水，避免再次遍历
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
};

17. 733. 图像渲染

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int oldColor=image[sr][sc];
        if(oldColor!=newColor){
            dfs(image,sr,sc,oldColor,newColor);
        }
        return image;
    }

    void dfs(vector<vector<int>>& image,int i,int j,int oldColor,int newColor){
        int m=image.size(),n=image[0].size();
        if(i<0||i>=m||j<0||j>=n){
            return;
        }
        if(image[i][j]!=oldColor){
            return;
        }
        image[i][j]=newColor;
        dfs(image,i,j-1,oldColor,newColor);
        dfs(image,i,j+1,oldColor,newColor);
        dfs(image,i-1,j,oldColor,newColor);
        dfs(image,i+1,j,oldColor,newColor);
    }
};

18. 1254. 统计封闭岛屿的数目

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int result=0;
        //靠边的岛屿不算封闭岛屿，先去掉
        for(int i=0;i<m;i++){
            dfs(grid,i,0);
            dfs(grid,i,n-1);
        }
        for(int j=0;j<n;j++){
            dfs(grid,0,j);
            dfs(grid,m-1,j);
        }
        //剩下的都是封闭岛屿
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    result++;
                    dfs(grid,i,j);
                }
            }
        }
        return result;
    }

    void dfs(vector<vector<int>>& grid,int i,int j){
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n){
            return;
        }
        if(grid[i][j]==1){
            return;
        }
        grid[i][j]=1;
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
};

19. 695. 岛屿的最大面积

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int result=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    result=max(result,dfs(grid,i,j));
                }
            }
        }
        return result;
    }
    int dfs(vector<vector<int>>& grid,int i,int j){
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n){
            return 0;
        }
        if(grid[i][j]==0){
            return 0;
        }
        grid[i][j]=0;
        return dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1)+1;
    }
};

20. 1905. 统计子岛屿

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m=grid1.size(),n=grid1[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid1[i][j]==0&&grid2[i][j]==1){
                    //这个肯定不是岛屿，1中没有，2中有,淹没掉2
                    dfs(grid2,i,j);
                }
            }
        }
        //2中剩下的都是子岛
        int result=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid2[i][j]==1){
                    result++;
                    dfs(grid2,i,j);
                }
            }
        }
        return result;
    }

    void dfs(vector<vector<int>>& grid, int i, int j){
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n){
            return;
        }
        if(grid[i][j]==0){
            return ;
        }
        grid[i][j]=0;
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
};