代码随想录day25 回溯4

491.递增子序列

思路:

1.本题需要在原有的顺序上进行，不能排序。而且对同一父节点下，本层使用过的元素在后面不能再使用，因为同样的值可能是分开的，所以考虑用哈希表记录。

2.因为本题的数字大小确定，考虑用数组记录。映射值=值+100.

3.这个数组不需要回溯，因为for里面的每一层都是横向的，只有纵向（backtracking）后才需要回溯，回溯到没有加入这个元素之前。

注意：for里面，最好是if里面写continue，否则容易写不全。

代码：

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    void backtracking(vector<int>&nums,int startIndex){
        if(path.size()>=2)res.push_back(path);
        //同一父节点下，本层的使用了a，别的就不能再使用a了
        //所以用unordered_set去重，固定范围所以用数组.-100->100,映射的时候加100即可
        int a[201]={0};
        for(int i=startIndex;i<nums.size();i++){
            if((path.size()!=0&&nums[i]<path.back())||a[nums[i]+100]==1){
                continue;
            }
                path.push_back(nums[i]);
                a[nums[i]+100]=1;
                backtracking(nums,i+1);
                path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        res.clear();
        path.clear();
        backtracking(nums,0);
        return res;
    }
};

46.全排列

思路:

1.排列问题，不需要startIndex，只需要一个used数组记录是否使用过。

2.停止条件：如果path的size==nums，return

4.单层逻辑：如果用过的，则continue；没用过则加入，改used值，递归，回溯

注意：

代码：

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    void backtracking(vector<int>& nums,vector<bool>&used){
        if(path.size()==nums.size()){
            res.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) {
        res.clear();
        path.clear();
        vector<bool>used(nums.size(),false);
        backtracking(nums,used);
        return res;
    }
};

47.全排列 II

思路:

1.在排列的基础上，去除同一父节点下的重复的

2.停止条件还是path的size跟nums的相等

3.单层逻辑：

如果是竖着的已经使用过的，continue

如果是横着使用过的，continue

否则正常逻辑

注意：需要先排列才可以这样用！！如果不能排列的就要用unordered_set代替

代码：

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    //去重逻辑：同一父节点的本层用过了一个，后面的就不能用了
    void backtracking(vector<int>&nums,vector<bool>used){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]==true)continue;
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)continue;
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        path.clear();
        sort(nums.begin(),nums.end());
        vector<bool>used(nums.size(),false);
        backtracking(nums,used);
        return res;
    }
};

332.重新安排行程（可跳过）

思路:

分析题目：我们需要一个能表示机票的数据结构，这个机票要包含开始地，目的地，到这个目的地的机票数量。所以考虑：unordered_map<string,map<string,int>>

含义：unordered_map<起始地,map<目的地,起始到目的地的机票张数>>

终止条件：res的值==总机票张数加1

返回值：bool，因为只需要找到排序好的第一条就可以返回了

单层逻辑：

如果这个目的地的机票数大于0，则加入，记录，递归，回溯。

注意这里，if(backtracking(ticketsNum))return true;如果这条路是对的，则返回，否则在for的外面return false；

注意：遍历的写法：

for(pair <const string,int>&t :target[res[res.size()-1]])

 for(const vector<string>&vec :tickets)

且主函数中需要初始化target和res

代码：

class Solution {
public:
    //含义：出发机场，《到达机场，几张到达这个机场的票》
    unordered_map<string,map<string,int>>target;
    vector<string>res;
    bool backtracking(int ticketsNum){
        if(res.size()==ticketsNum+1)return true;
        for(pair <const string,int>&t :target[res[res.size()-1]]){//即result的最后一个元素，即起始地
            if(t.second>0){
                res.push_back(t.first);
                t.second--;
                //这里需要return true，因为如果这个路是通的，则return true
                if(backtracking(ticketsNum))return true;
                t.second++;
                res.pop_back();
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        target.clear();
        res.clear();
        res.push_back("JFK");
        for(const vector<string>&vec :tickets){
            target[vec[0]][vec[1]]++;
        }
        backtracking(tickets.size());
        return res;
    }
};

51.N皇后（适当跳过）

思路:

1.参数类型：void，n，row，chessboard（这个不可以用全局变量，因为对chessboard的初始化需要有n才能做）

2.回溯还是一样思路，注意：递归深度控制行，for里面控制列

如果row==n，则pushback。

单层：遍历col，如果合法，进行操作

3.合法函数：

先对该列进行搜查，然后对45度角，然后对135度角。

注意：

代码：

class Solution {
public:
    vector<vector<string>>res;
    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;
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chessboard[i][j]=='Q')return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(chessboard[i][j]=='Q')return false;
        }
        return true;
    }
    void backtracking(int n,int row,vector<string>&chessboard){
        if(row==n){
            res.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]='.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        res.clear();
        vector<string>chessboard(n,string(n,'.'));
        backtracking(n,0,chessboard);
        return res;
    }
};

37.解数独（适当跳过）

思路:

1.跟N皇后的思路差不多

2.isValid，判断即可。分为行，列，九宫格

3.只需要找到一个，所以类型为bool，因为主函数的是void，所以在board上改就行。

参数不需要row，col，因为由for循环进行行+列的遍历，每个数都尝试。

注意：backtracking里面每个for循环结束后，是否要return true或者false；

代码：

class Solution {
public:
    bool isValid(int row,int col,char n,vector<vector<char>>&board){
        //行
        for(int i=0;i<9;i++){
            if(board[row][i]==n)return false;
        }
        //列
        for(int i=0;i<9;i++){
            if(board[i][col]==n)return false;
        }
        //九宫格
        int r=(row/3)*3,c=(col/3)*3;
        for(int i=r;i<r+3;i++){
            for(int j=c;j<c+3;j++){
                if(board[i][j]==n)return false;
            }
        }
        return true;

    }
    bool backtracking(vector<vector<char>>&board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;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;//9个数都试过了且没有找到，return false
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

总结

看代码随想录总结即可

自己心得：

组合问题：需要n个for循环，横向遍历+纵向。获取的是树叶

        去重逻辑：纵向/横向。善用used数组

切割问题：回文串，IP地址

子集问题：获取树的每个结点

如果要写终止条件，注意：result.push_back(path);要放在终止条件的上面，如下：

result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉结果
if (startIndex >= nums.size()) { // 终止条件可以不加
    return;
}

排列问题;不需要satrtIndex，只需要used数组

去重问题：可以重新排序的，用used。不可以的则用哈希表，能确定范围的用数组更快。