回溯算法

子集问题

①res,path; backtracking函数
②无递归终止条件判断,直接path存入res;
③递归需要startIndex;
④(补充)“有重复元素、不能包含重复的解集” 在for循环多加判断条件:i>0 && used[i-1]==false && nums[i]==nums[i-1] 跳过同层重复元素的处理

  1. 78. 子集
    递归终止条件可以省略(与for循环的判断条件一致),每次递归调用的时候先把结果写入到res中
  2. 90. 子集 II
    此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。其他没有什么强调的了。

78. 子集
递归终止条件可以省略(与for循环的判断条件一致),每次递归调用的时候先把结果写入到res中

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

    void backtracking(vector<int>& nums, int startIndex) {
        res.push_back(path);

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

90. 子集 II
此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex, vector<bool>& used) {
        res.push_back(path);

        for(int i=startIndex;i<nums.size();i++) {
            if(i>0 && used[i-1]==false && nums[i]==nums[i-1]) {
                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 res;
    }
};

排列问题

全排列需要对所有元素进行排列,
①终止条件:path.size == nums.size()
②for遍历元素集合为所有元素,用used控制不重复
③有重复元素,要求解集不重复的处理条件:i>0 && nums[i]==nums[i-1] && used[i-1]==false

  1. 46. 全排列
    排列问题,path写入res中一定是包含了nums的所有元素,只是排列顺序不同
    遍历的元素集合为所有元素,只是需要used数组,标记已使用过的元素避免出现重复
  2. 47. 全排列 II
    还是强调对于不重复解集的处理

46. 全排列
排列问题,path写入res中一定是包含了nums的所有元素,只是排列顺序不同
遍历的元素集合为所有元素,只是需要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);
        }

        for(int i=0;i<nums.size();i++) {
            if(used[i]==true)
                continue;
            path.push_back(nums[i]);
            used[i]=true;
            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 res;
    }
};

47. 全排列 II
还是强调对于不重复解集的处理

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);
        }
        for(int i=0;i<nums.size();i++) {
            if(used[i]==true) {
                continue;
            }else if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){
                continue;
            }
            path.push_back(nums[i]);
            used[i]=true;
            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 res;
    }
};

棋盘问题

需要定义棋盘(或题目给出),一层or两层循环(看题目逻辑),单独的isValid函数判断放置是否合理
①backtracking函数,棋盘选择按行递归或者逐元素递归
②isValid函数判断放置是否合理

  1. 51. N 皇后
    1.构建棋盘 vector chessboard(n,string(n,‘.’));
    2.逐行使用回溯,使用isValid函数判断放置位置是否合理
    3.isValid函数,判断列、45度方向、135度方向放置是否合理
  2. 37. 解数独
    1.双层循环,i j定位到要放数字的点,isValid判断是否符合逻辑,使用回溯递归调用
    2.isValid判断行、列,以及内部小九格是否有重复数字

51. N 皇后
1.构建棋盘 vector chessboard(n,string(n,‘.’));
2.逐行使用回溯,使用isValid函数判断放置位置是否合理
3.isValid函数,判断列、45度方向、135度方向放置是否合理

class Solution {
public:
    vector<vector<string>> res;
    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] = '.';
            }
        }
    }
    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;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));
        backtracking(n,0,chessboard);
        return res;
    }
};

37. 解数独
1.双层循环,i j定位到要放数字的点,isValid判断是否符合逻辑,使用回溯递归调用
2.isValid判断行、列,以及内部小九格是否有重复数字

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]=='.') {
                    for(char c = '1';c<='9';c++) {
                        if(isValid(i,j,c,board)) {
                            board[i][j]=c;
                            if(backtracking(board)) {
                                return true;
                            }board[i][j]='.';
                        }
                            
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(int row,int col,char k,vector<vector<char>>& board) {
        for(int i=0;i<9;i++) {
            if(board[row][i] == k)
                return false;
        }
        for(int i=0;i<9;i++) {
            if(board[i][col] == k)
                return false;
        }
        
        int row_1 = (row/3)*3;
        int col_1 = (col/3)*3;
        for(int i=row_1;i<row_1+3;i++) {
            for(int j=col_1;j<col_1+3;j++) {
                if(board[i][j]==k)
                    return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部