自学内容网 自学内容网

回溯法经典难题解析

本文将通过几个经典的回溯问题,展示回溯算法的应用及其在解决问题时的核心思想和技巧。这些问题包括全排列、全排列II、N皇后以及数独问题,本文将分别介绍每个问题的思路与实现。

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

思路:
对于给定的数组,我们通过回溯法逐一选择数组中的元素,并将其加入当前的排列中。
需要一个 visited 数组来记录每个元素是否已经被使用过,避免重复排列。
每当排列的长度等于原数组长度时,表示当前排列已完成,加入结果集。

核心技巧:
在递归过程中使用 visited 数组来确保每个元素只被使用一次。
递归的终止条件是当当前排列的长度等于数组长度时,说明已经形成一个完整的排列。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    unordered_set<int> node;
    void backfind(vector<int>& nums){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++){
            if(node.find(nums[i])!=node.end()){continue;}
            node.insert(nums[i]);
            path.push_back(nums[i]);
            backfind(nums);
            node.erase(nums[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        backfind(nums);
        return res;
    }
};

47. 全排列 II

给定一个可包含重复数字的序列 nums按任意顺序 返回所有不重复的全排列。

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路:先对数组进行排序,使得相同的元素相邻。使用 visited 数组来标记每个元素是否已经被访问过,同时利用排序后的数组来跳过已经处理过的重复元素。在每次递归时,检查当前元素与前一个元素是否相同,如果相同且前一个元素未被访问,则跳过当前元素。

核心技巧:排序保证了相同元素相邻,从而避免了重复排列。通过回溯的剪枝技巧,避免在同一层的递归中重复访问相同的元素。
47.全排列II1

47.全排列II3

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backfind(vector<int>& nums, vector<bool>& visited){
        if(path.size()==nums.size()){
            res.push_back(path);
            return; 
        }
        for(int i=0; i<nums.size(); i++){
            if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false){continue;}
            //同层树重复的跳过,同层的上一个visited是没访问过的(回溯)
            //visited[i-1]==true也是可以滴
            if(visited[i]){continue;}
            visited[i]=true;
            path.push_back(nums[i]);
            backfind(nums,visited);
            visited[i]=false;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> visited(nums.size(), false);
        backfind(nums,visited);
        return res;
    }
};

51. N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

示例 1:

img

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

思路:使用回溯法逐行放置皇后,每放置一个皇后就递归处理下一行。
在每次尝试放置皇后时,检查该位置是否会与已放置的皇后发生冲突,即检查同列、左斜线和右斜线是否已有皇后。

核心技巧:使用三种标记(列标记、左斜线标记、右斜线标记)来有效判断是否可以放置皇后。
通过递归实现行的逐步尝试,并在放置皇后后继续处理下一行。

51.N皇后

class Solution {
public:
    vector<vector<string>> res;
    void find(int n, int row, vector<string>& rowChess){
        if(row==n){
            res.push_back(rowChess);
            return;
        }
        for(int col=0; col<n; col++){
            if(isQ(rowChess,row,col,n)){
                rowChess[row][col]='Q';
                find(n, row+1, rowChess);
                rowChess[row][col]='.';
            }
        }
    }

    bool isQ(vector<string>& rowChess, int row, int col, int n){
        //先遍历列
        for(int i=0; i<row; i++){
            if(rowChess[i][col]=='Q'){
                return false;
            }
        }
        //再检查45°线
        for(int i=row-1, j=col-1; i>=0&&j>=0; i--,j--){
            if(rowChess[i][j]=='Q'){
                return false;
            }
        }
        //再检查135°线
        for(int i=row-1, j=col+1; i>=0&&j<n; i--,j++){
            if(rowChess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> rowChess(n, string(n,'.'));
        find(n, 0, rowChess);
        return res;
    }
};

37. 解数独

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.' 表示。

思路:使用回溯法逐步填充数独中的空格。每次选择一个空格,尝试填入数字 1-9,并检查填入的数字是否合法。如果合法,递归处理下一个空格;如果不合法,回溯并尝试其他数字。

核心技巧:使用一个 isOK 函数来检查当前填入的数字是否符合数独的规则。
回溯的终止条件是所有空格都被填充且合法时,返回解。

class Solution {
public:
    bool backsolve(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(isOK(board,i,j,c)){
                            board[i][j]=c;
                            if(backsolve(board)) return true;
                            board[i][j]='.';
                        }
                    }return false;
                }
                
            }
        }return true;
    }

    bool isOK(vector<vector<char>>& board, int row, int col, char val){
        //行里面寻找有没有重复的
        for(int i=0; i<9; i++){
            if(board[i][col]==val){
                return false;
            }
        }
        //列里面寻找有没有重复的
        for(int j=0; j<9; j++){
            if(board[row][j]==val){
                return false;
            }
        }
        int startrow=(row/3)*3;
        int startcol=(col/3)*3;
        for(int i=startrow; i<startrow+3; i++){
            for(int j=startcol; j<startcol+3; j++){
                if(board[i][j]==val){
                    return false;
                }
            }
        }
        return true;
    }

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

原文地址:https://blog.csdn.net/Hhjhj255/article/details/144001317

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!