经典回溯

N皇后问题、复原IP地址、解数独

N皇后问题

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        //'.'表示空，'Q'表示皇后，初始化空棋盘
        vector<string> board(n,string(n,'.'));
        backtrack(board,0);
        return res;
    }
    //路径：board中小于row的那些行都已经成功放置了皇后
    //选择列表：第row行的所有列都是放置皇后的选择
    //结束条件：row超过board的最后一行，说明棋盘放满了
    void backtrack(vector<string>& board, int row){
        //触发结束条件
        if(row==board.size()){
            res.push_back(board);
            return;
        }
        int n=board[row].size();
        for(int col=0; col<n;col++){
            //排除不合法选择
            if(!isValid(board, row, col)) continue;
            // 做选择
            board[row][col]='Q';
            //回溯 进行下一行决策
            backtrack(board, row+1);
            //撤销选择
            board[row][col]='.';
        }
    }
    //是否可以在board[row][col]放置皇后
    bool isValid(vector<string>& board, int row, int col){
        int n=board.size();
        //检查列中是否有皇后互相冲突
        for(int i=0;i<row;i++){
            if(board[i][col]=='Q') return false;
        }
        //检查右上方是否有皇后互相冲突
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(board[i][j]=='Q') return false;
        }
        //检查左上方是否有皇后冲突
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board[i][j]=='Q') return false;
        }
        return true;
    }

};

93.复原IP地址

class Solution {
public:
    vector<string> res;
    string temp;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0);
        return res;
    }
    void dfs(string s, int cnt, int index){
        if(cnt==4 && index==s.size()){ // 片段满4段，且耗尽所有字符
            res.push_back(temp.substr(0, temp.size()-1));
            return;
        }
        for(int i=1;i<=3;i++){   // 只能存长度1~3的字符串
            if(index+i>s.size()) return;   //超出范围
            if(s[index]=='0' && i!=1) return;  //0x, 00x非法
            if(i==3 && s.substr(index, i)>"255") return;   //不能大于255

            //做选择
            temp += s.substr(index, i);
            temp.push_back('.');
            //回溯
            dfs(s, cnt+1, index+i);
            //撤销
            temp = temp.substr(0, temp.size()-i-1);
        }
    }
};

37. 解数独

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char>>& board, int i, int j){
        int m=9;
        int n=9;
        if(i==m){
            return true;
        }
        if(j==n){
            return dfs(board, i+1, 0);   
        }
        if(board[i][j]!='.'){
            return dfs(board, i, j+1);
        }
        for(char ch='1';ch<='9';ch++){
            if(!isValid(board, i, j, ch)) continue;
            //做选择
            board[i][j] = ch;
            if(dfs(board, i, j+1)) return true;
            //撤销选择
            board[i][j] = '.';
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int r, int c, char n){
        for(int i=0;i<9;i++){
            //判断行是否存在重复
            if(board[r][i] == n) return false;
            //判断列是否存在重复
            if(board[i][c] == n) return false;
            //判断3*3方框是否存在重复
            if(board[(r/3)*3+i/3][(c/3)*3+i%3]==n) return false;
        }
        return true;
    }
};