leetcode题解(递归和回溯法)

在计算机问题中，大量的问题都需要使用递归算法，上一篇博客我们介绍了一下二叉树中的递归问题。现在我们来看递归算法中非常经典的思想回溯法，这样的算法思想通常都应用在一类问题上，这类问题叫做树型问题，这类问题他本身没有定义在一颗二叉树中，但我们具体分析这个问题时就会发现解决这个问题的思路本质是一颗树的形状。

树形问题

现在我们来看递归算法中非常经典的思想回溯法，这样的算法思想通常都应用在一类问题上，这类问题叫做树型问题，这类问题他本身没有定义在一颗二叉树中，但我们具体分析这个问题时就会发现解决这个问题的思路本质是一颗树的形状。

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

解题思路

比如我们输入的digits=“23”，2能代表abc三个字母，当2代表a时，3代表def，同理我们就可以画出一棵树。

递归过程：

digits是数字字符串

s(digits)是digits所能代表的字母字符串

s(digits[0…n-1]) = letter(digits[0]) + s(digits[1…n-1]) = letter(digits[0]) + letter(digits[1]) + s(digits[2…n-1]) = …

代码实现

class Solution {
private:
    const string letterMap[10] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    
    vector<string> res;
    
    //index表示从该数字开始在字串，存于s中
    // s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
    // 寻找和digits[index]匹配的字母, 获得digits[0...index]翻译得到的解
    void findCombination(const string &digits, int index, const string &s){
        if (index == digits.size()){
            res.push_back(s);
            return;
        }
        
        //获得数字
        char c = digits[index];
        //对应的字母串
        string letters = letterMap[c - '0'];
        
        for (int i = 0; i < letters.size(); i++){
            findCombination(digits, index + 1, s + letters[i]);
        }
        return ;
    }
    
public:
    vector<string> letterCombinations(string digits) {
        res.clear();
        if (digits.size() == 0){
            return res;
        }
        
        findCombination(digits, 0, "");
        return res;
    }
};
复制代码

什么是回溯

递归调用的一个重要特征-要返回。回溯法是暴力解法的一个主要实现手段。

思考题

• leetcode 93
• leetcode 131

组合问题(Permutations)

leetcode 46. 全排列

解题思路

回溯算法能处理一类重要的问题是排列问题，如果我们要用1,2,3进行排列，我们可以先抽出一个元素，比如我们现在抽出1，那么我们下面要做的事就是使用2,3两个元素构造排列。我们又需要抽出一个元素，如果我们抽出2，我们剩下唯一的元素就是3，我们通过这个路径获得排列123，用23排列如果选3，那么就剩下2我们得到排列132。相应的我们考虑最开始选择2或者选择3。

这也是一个树形问题

Perms(nums[0…n-1]) = {取出一个数字} + Perms(nums[{0…n-1} - 这个数字])

代码实现

class Solution {
private:
    vector<vector<int>> res;
    vector<bool> visitor;
    //产生一个解
    //p[0, index-1]已经是一个组合了
    //要生成index大小的组合
    // p中保存了一个有index-1个元素的排列。
    // 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
    void generatePermute(const vector<int>& nums, int index, vector<int>& p){
        if (index == nums.size()){
            res.push_back(p);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++){
            if (!visitor[i]){
                p.push_back(nums[i]);
                visitor[i] = true;
                generatePermute(nums, index + 1, p);
                
                //回溯
                p.pop_back();
                visitor[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        if (nums.size() == 0){
            return res;
        }
        visitor = vector<bool>(nums.size(), false);
        vector<int> p;
        generatePermute(nums, 0, p);
        
        return res;
    }
};

复制代码

相似问题

• leetcode 47

组合问题 Combinations

回溯的意思就是要回去，递归函数自动保证了回去，但是我们设置的其他变量如果有必要的话也必须要回到原位。

leetcode 77. 组合

解题思路

我们在1，2，3，4中取出你两个数。在第一步时如果我们取1，那么接下来就在2，3，4中取一个数，我们可以得到组合12，13，14。如果第一步取2，那么第二步在3，4中取一个数，可以得到组合23，24。如果我们第一步取3，那么第二步只能取4，得到组合34。

代码实现

class Solution {
    
private:
    vector<vector<int>> res;
    //前start-1个组合已经完成
    // 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
    void generateCombinations(int n, int k, int start, vector<int> &c){
        if (c.size() == k){
            res.push_back(c);
            return;
        }
        
        for (int i = start; i <= n; i++){
            c.push_back(i);
            generateCombinations(n, k , i+1, c);
            
            //回溯
            c.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> combine(int n, int k) {
        res.clear();
        
        if (n <= 0 || k <= 0){
            return res;
        }
        vector<int> c;
        generateCombinations(n, k, 1, c);
        return res;
    }
};
复制代码

回溯法解决组合问题的优化

这是我们对这道题递归树建立的模型，在这个模型里存在一个地方我们是明显没必要去走的，就是在于最后的地方，我们根本不需要去尝试取4，这是因为我们取4之后无法再取任意一个数了。在我们上面的算法中我们还是尝试取了4，取完4之后当取第二个数时发现我们什么都取不了了，所以只好再返回回去，对于这一部分我们完全可以把它剪掉。换句话说，我们只尝试取1,2,3。

回溯法的剪枝

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution {
    private:
        vector<vector<int>> res;
    
        // 求解C(n,k), 当前已经找到的组合存储在c中, 需要从start开始搜索新的元素
        void generateCombinations(int n, int k, int start, vector<int> &c){
    
            if( c.size() == k ){
                res.push_back(c);
                return;
            }
    
            // 还有k - c.size()个空位, 所以,[i...n]中至少要有k-c.size()个元素
            // i最多为 n - (k-c.size()) + 1
            for( int i = start ; i <= n - (k-c.size()) + 1 ; i ++ ){
                c.push_back( i );
                generateCombinations(n, k, i + 1 , c );
                c.pop_back();
            }
    
            return;
        }
    public:
        vector<vector<int>> combine(int n, int k) {
    
            res.clear();
            if( n <= 0 || k <= 0 || k > n )
                return res;
    
            vector<int> c;
            generateCombinations(n, k, 1, c);
    
            return res;
        }
    };
    
复制代码

相似问题

• leetcode 39
• leetcode 40
• leetcode 216
• leetcode 78
• leetcode 90
• leetcode 401

二维平面上的回溯法

leetcode79. 单词搜索

解题思路

对于每一个位置，我们按照上右下左从四个方向寻找，当选择的方向匹配时，则选择这个位置继续进行上右下左寻找，如果四个方向都不匹配，则退回上一步的位置寻找下一个方向。

代码实现

class Solution {

//从board[startx][starty]开始， 寻找[index...word.size()]
private:
    vector<vector<bool>> visited;
    int m,n;//行与列
    int d[4][2] = {{-1,0}, {0, 1}, {1, 0}, {0, -1}};
    
    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    bool searchWord(vector<vector<char>>& board, string word, int index, int startx, int starty){
    
    //寻找到最后一个元素了
    if (index == (word.size() -1)){
        return board[startx][starty] == word[index];
    }
    
    if (board[startx][starty] == word[index]){
        visited[startx][starty] = true;
        
        // 从startx, starty出发,向四个方向寻
        for (int i = 0; i < 4; i++){
            int newx = startx + d[i][0];
            int newy = starty + d[i][1];
            
            if(inArea(newx, newy) && !visited[newx][newy]){
                if (searchWord(board, word, index + 1, newx, newy)){
                    return true;
                }
            }
        }
        
        //回溯
        visited[startx][starty] = false;
    }
    
    return false;
}
    
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        assert(m > 0);
        n = board[0].size();
        
        //初始化visitor
        for (int i = 0; i < m ; i++){
            visited.push_back(vector<bool>(n, false));
        }
        
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (searchWord(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
};

复制代码

floodfill算法，一类经典问题

leetcode 200. 岛屿的个数

解题思路

首先我们从二维数组最开始的地方(0,0)找起，这个地方是1，我们就找到了一个新的岛屿，但我们需要标记和这块陆地同属于一个岛屿的陆地，当我们寻找下一个岛屿的时候才不会重复。那么这个过程就是floodfill过程。其实就是从初始点开始进行一次深度优先遍历，和上面那道题的寻找很相似，对每一个岛屿进行四个方向寻找。

代码实现

class Solution {

private:
    int d[4][2] = {{0,1}, {0, -1}, {1,0},{-1, 0}};
    int m, n;
    vector<vector<bool>> visited;
    
    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    void dfs(vector<vector<char>>& grid, int x, int y){
        visited[x][y] = true;
        
        for (int i = 0; i < 4; i++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            
            if (inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1'){
                dfs(grid, newx, newy);
            }
        }
        
        return;
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        if (m == 0){
            return 0;
        }
        n = grid[0].size();
        
        if (n == 0){
            return 0;
        }
        
        for (int i = 0; i < m; i++){
            visited.push_back(vector<bool>(n, false));
        }
        
        int res = 0;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == '1' && !visited[i][j]){
                    dfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }
};
复制代码

在这里，我们似乎没有看见回溯的过程，也就是说我们不需要找到一个位置让visited[x][y]为false,这是因为我们的目的就是要把和最初我们运行的(i,j)这个点相连接的岛屿全部标记上，而不是在其中找到某一个特定的序列或者一个具体的值，所以我们只标记true,不会把它倒着标记成false。所以对于这个问题是否叫做回溯法，这是一个见仁见智的问题。在搜索的过程中一定会回去，这是递归的特性。但它没有对信息进行重置。不过它的解题思路是经典的floodfill。

相似问题

• leetcode 130
• leetcode 417

回溯法是经典人工智能的基础

回溯法师经典人工智能的基础

leetcode 51. N皇后

解题思路

**快速判断合法的情况

• dia1: 横纵坐标相加相同

• dia2:横坐标-纵坐标相同

对于四皇后为例看一下如何递归回溯。首先肯定每行都应该有一个皇后，否则就会有一行出现多个皇后。那么第二行只能在第三个位置或第四个位置，考虑第三个位置。那么第三行无论在哪都会有冲突。说明我们第二行的皇后不能放在第三个位置，我们回溯，在第四个位置放置皇后。

每一次在一行中尝试摆放一个皇后，来看我们能不能摆下这个皇后，如果不能摆下，回去上一行重新摆放上一行皇后的位置，直到我们在四行都摆放皇后。

代码实现

class Solution {
    
private:
    vector<bool> col, dia1, dia2;
    vector<vector<string>> res;
    
    //尝试在一个n皇后问题中，摆放第index行的皇后位置
    void putQueen(int n, int index, vector<int> &row){
        if (index == n){
            res.push_back(generateBoard(n, row));
            return;
        }
        
        // 尝试将第index行的皇后摆放在第i列
        for (int i = 0; i < n; i++){
            if (!col[i] && !dia1[index + i] && !dia2[index -i + n -1]){
                row.push_back(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index -i + n -1] = true;
                
                //递归,尝试下一行
                putQueen(n, index + 1, row);
                
                //回溯，复原
                col[i] = false;
                dia1[index + i] = false;
                dia2[index -i + n -1] = false;
                row.pop_back();
            }
        }
        return;
    }
    
    vector<string> generateBoard(int n, vector<int> &row){
        assert(n == row.size());
        vector<string> board(n, string(n, '.'));
        
        for(int i = 0; i < n; i++){
            board[i][row[i]] = 'Q';
        }
        
        return board;
    }
    
public:
    vector<vector<string>> solveNQueens(int n) {
        
        res.clear();
        col.clear();
        dia1.clear();
        dia2.clear();
        col = vector<bool>(n, false);
        dia1 = vector<bool>(2*n -1, false);
        dia2 = vector<bool>(2*n -1, false);
        vector<int> row;
        putQueen(n, 0, row);
        return res;
    }
};

复制代码