leetcode演算法之回溯

• 2021 年 2 月 5 日
• AI
• C/C++/C#

今天來盤一盤 **回溯 ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

回溯

回溯法其實就是暴力法。經常使用的暴力法就是多層循環， 但是面對樹形結構的話很難採用循環的方式進行遍歷。這時就要採用遞歸回溯的方法實現暴力法。

這類題目看似比較難，但是其實時很簡單規範的套路性的程式碼， 下邊幾道題會有一個固定的模板套路， 請耐心體會。

• 17 電話號碼的字母組合(medium)
• 93 復原IP地址（medium）
• 131 分割迴文串(medium)
• 46 全排列(medium)
• 47 全排列 II(medium)
• 77 組合(medium)
• 39 組合總和(medium)
• 40 組合總和 II
• 216 組合總和 III
• 78 子集(medium)
• 90 子集II(medium)
• 79 單詞搜索(medicum)
• 200 島嶼數量（medium）
• 130 被圍繞的區域(medium)
• 417 太平洋大西洋水流問題（medium)
• 51 N皇后（hard）
• 52 N皇后 II（hard）
• 37 解數獨（hard）

17 電話號碼的字母組合(medium)

• 一個樹形結構
• 例如輸入的數字為「23
• 那麼這棵樹的第一層有三個節點是 abc， 每個節點的下邊有三個節點def。遍歷這棵樹得到所有的路徑。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // 構建字典映射
        unordered_map<char, string> character2Num({
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        });
        // 定義返回值
        vector<string> res;
        string path;
        backtrace(digits, res, 0, path, character2Num);
        return res;
    }

    void backtrace(string digits, vector<string>& res, int index, string path, unordered_map<char, string>& character2Num){
        // 回溯遞歸函數
        if (digits.empty()) return ;
        // 如果遍歷完成所有的數字，就保存得到的字母組合。
        if (index == digits.size()) {
            res.push_back(path);
            return ;
        }
        // 得到某個數字映射得到的字元串
        auto characters = character2Num[digits[index]];
        // 遍歷這個字元串，相當於樹形結構中的一層
        for (int i = 0; i < characters.size(); i++){
            path += characters[i];
            // 向樹的下一層進行遍歷
            backtrace(digits, res, index + 1, path, character2Num);
            // 回溯到上一層的時候，需要去除這一層的元素。
            path.pop_back();
        }   
     }
};

93 復原IP地址（medium）

• 這個題也可以直接四層循環來做， 因為限制了最多分為4部分
• 這裡依然採用回溯搜索法來處理。這種分割字元串的題目，使用回溯法是一個通用的套路。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector< string> res;
        string path;

        backtrace(s, res, path, 0, 0);
        return res;
    }
    void backtrace(string& s, vector<string>& res, string path, int cnt, int startindex){
        // cnt表示分割的部分的數目，一共需要分割為4部分， startindex為接下來這一部分的開始位置
        if (cnt == 4){ 
            if (startindex == s.size())
                res.push_back(path);
            return;
        }
        
        for (int i = startindex; i < s.size(); i++){
            // 每一部分的最長長度為3
            if (i - startindex == 3) break;
            auto prepath = path;
            auto substring = s.substr(startindex, i - startindex + 1);
            // 如果長度部位0， 且開頭的數字為0， 不合法的ip
            if ( i - startindex > 0 && s[startindex] == '0') break;

            // 如果大於255直接返回。
            if (stoi(substring) > 255 ) break;
            path += substring;
            if (i != s.size() - 1)
                path += ".";
            backtrace(s, res, path, cnt+1, i + 1);
            path = prepath;
        }
    }
};

131 分割迴文串(medium)

• 與上一題思路差不多， 沒有上一題那麼多需要排除的邊界條件。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        // 得到所有的子字元串，判斷得到的是否都是迴文串。
        vector<vector<string>> res;
        vector<string> palstring;
        string path;

        backtrace(s, res, palstring, 0);
        return res;
    }
    void backtrace(string& s, vector<vector<string>>& res, vector<string>& palstring, int startindex){
        if (startindex == s.size()){
            res.push_back(palstring);
            return ;
        }
        for (int i = startindex; i < s.size(); i++){
            auto substring = s.substr(startindex, i - startindex + 1);
            if ( ! ispalindrome(substring)) continue;
            palstring.push_back(substring);
            backtrace(s, res, palstring, i + 1);
            palstring.pop_back();
        }

    }
    bool ispalindrome(string s){
        int l = 0, r = s.size() - 1;
        while ( l < r){
            if (s[l] != s[r])
                return false;
            l++; r--;
        }
        return true;
    }

};

46 全排列(medium)

• 依然是一個樹形結構，標準的回溯法套路程式碼

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

47 全排列 II(medium)

• 與上一題的不同之處在於，這裡存在重複的數字
• 也就是說如果在同一層中出現了相同的數字，那麼會出現重複的情況。
• 採用排序的方式去重。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        vector< vector<int> > res;
        unordered_set<int> visited;
        backtrace(nums, res, path, visited, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, unordered_set<int>& visited, int index){
        if (index == nums.size()){
            res.push_back(path);
            return ;
        }
        for (int i=0; i< nums.size(); i++){
            if (visited.find(i) != visited.end()) continue;
            // 這裡採用nums中第i-1個元素如果沒有訪問過，說明在之後依然會出現，造成重複。
            if (i > 0 && nums[i] == nums[i-1] && visited.find(i - 1) == visited.end()) continue;
            visited.insert(i);
            path.push_back(nums[i]);
            backtrace(nums, res, path, visited, index+1);
            path.pop_back();
            visited.erase(i);
        }
    }
};

77 組合(medium)

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        baketrace(n, k, 0, res, path);
        return res;
    }
    void baketrace(int n, int k, int index, vector<vector<int>>& res, vector<int>& path){
        if (k == 0){
            res.push_back(path);
            return;
        }
        // 如果剩餘的數字不夠組成k個數字的組合，那麼直接返回
        if (n - index + 1 < k) return ;

        for(int i = 1; i <= n; i++){
            if (i <= index) continue;
            path.push_back(i);
            baketrace(n, k-1, i, res, path);
            path.pop_back();
        }
    }
};

39 組合總和(medium)

• 與上一題的主要不同點在於一個元素可以多次選擇，因此這裡層的起始索引不再是i+1，而是i

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;
        
        backtrace(candidates, res, path, target, 0);
        return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, int target, int index){
        if (target == 0){
            res.push_back(path);
            return ;
        }
        for (int i = 0; i< candidates.size(); i++){
            if (candidates[i] > target) continue;
            if (i < index) continue;
            path.push_back(candidates[i]);
            backtrace(candidates, res, path, target- candidates[i], i);
            path.pop_back();
        }
    }
};

40 組合總和 II

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    // 每個數字只可以使用一次，並且可能含有重複的數字
    vector<vector<int>> res;
    vector<int> path;
    // 排序去重
    sort(candidates.begin(), candidates.end());
    unordered_set<int> visited;
    backtrace(candidates, res,  path, visited, 0, target);
    return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, unordered_set<int>& visited, int index, int target){
        if(target == 0){
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++){
            
            if (candidates[i] > target) break;
            if ( i > 0 && candidates[i] == candidates[i-1] && visited.find(i-1) == visited.end()) continue;
            path.push_back(candidates[i]);
            visited.insert(i);
            backtrace(candidates, res, path, visited, i+1, target - candidates[i]);
            path.pop_back();
            visited.erase(i);
        }
    }
};

216 組合總和 III

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        if ( k > 9 || n > 45) return {};
        vector<vector<int>> res;
        vector<int> path;
        vector<int> candidates({1,2,3,4,5,6,7,8,9});
        backtrace(candidates, res,  path,  0, n, k);
        return res;
    }
    void backtrace(vector<int>& candidates, vector<vector<int>>&res, vector<int>& path, int index, int target, int depth){
        if(target == 0 && depth == 0){
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++){
            if (candidates[i] > target) break;
            path.push_back(candidates[i]);
            backtrace(candidates, res, path, i+1, target - candidates[i], depth-1);
            path.pop_back();
        }
    }
};

78 子集(medium)

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrace(nums, res, path, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path, int index ){

        res.push_back(path);

        for (int i = index; i < nums.size(); i++){
            path.push_back(nums[i]);
            backtrace(nums, res, path, i+1);
            path.pop_back();
        }
    }
};

90 子集II(medium)

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 同一層中不能有相同的元素， 排序去重
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        unordered_set<int> visited;
        backtrace(nums, res, path, visited, 0);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& path,unordered_set<int>& visited, int index){
        res.push_back(path);
        for (int i = index; i< nums.size(); i++){
            if (i > 0 && nums[i] == nums[i-1] && visited.find(i - 1) == visited.end()) continue;
            visited.insert(i);
            path.push_back(nums[i]);
            backtrace(nums, res, path, visited, i + 1);
            path.pop_back();
            visited.erase(i);
        }
    }
};

• 下邊的幾道搜索的問題，也是一類非常經典的回溯問題。

79 單詞搜索(medicum)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<pair<int, int>> offsets({ {-1, 0}, {0, 1}, {1, 0}, {0 ,-1} });
        vector<vector<int>> visited(board.size(), vector<int>(board[0].size(), 0));

        for (int i = 0; i< board.size(); i++){
            for (int j = 0; j< board[0].size(); j++){
                if (board[i][j] == word[0]){
                    if (backtrace(board, word, visited, offsets, i, j, 1))
                        return true;
                }
            }
        }
        return false;
    }

    bool backtrace(vector<vector<char>>& board, string& word, vector<vector<int>>& visited, vector<pair<int, int>>& offsets, int x, int y, int index){
        // if (board[x][y] != word[index]) return false;
        visited[x][y] = 1;

        if (index == word.size()) return true;

        for (auto off :offsets){

            int new_x = x + off.first;
            int new_y = y + off.second;

            if (!inboard(board, new_x, new_y)) continue;

            if (visited[new_x][new_y] == 1) continue;

            if (board[new_x][new_y] != word[index]) continue;

            if (backtrace(board, word, visited, offsets, new_x, new_y, index + 1))
                return true;
        }
        visited[x][y] = 0;
        return false;
    }
    bool inboard(vector<vector<char>>& board, int x, int y){
        return (x >= 0 && x < board.size()) && ( y >= 0 && y < board[0].size());
    }
};

200 島嶼數量（medium）

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        vector<pair<int, int>> offsets({ {-1, 0},{1, 0}, {0, 1}, {0, -1} });
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == '1'){
                    res++;
                    backtrace(grid, i, j, m, n, offsets);
                }
            }
        }
        return res;
    }
    void backtrace(vector<vector<char>>& grid, int x, int y, int m, int n, vector<pair<int,int>>& offsets){
        grid[x][y] = '0';
        for (auto off: offsets){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (!inboard(m, n, new_x, new_y) || grid[new_x][new_y] == '0') continue;
            backtrace(grid, new_x, new_y, m, n, offsets);
        }    
    }

    bool inboard(int m, int n, int x, int y){
        return (x >= 0 && x < m) && (y >= 0 && y < n);
    }
};

130 被圍繞的區域(medium)

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        //找到與邊界聯通的O，標記為o，然後將剩餘的O變為x，o變為O即可
        if (board.empty()) return ;
        vector<pair<int, int>> offsets({{1, 0},{-1, 0}, {0, 1}, {0, -1}});
        int m = board.size(), n = board[0].size();
        // 遍歷邊界
        for ( int i = 0; i< m; i++){
            if (board[i][0] == 'O')
                backtrace(board, i, 0, offsets);
            if (board[i][n-1] == 'O')
                backtrace(board, i, n-1, offsets);
        }
        for (int j = 0; j < n; j++){
            if (board[0][j] == 'O')
                backtrace(board, 0, j, offsets);
            if (board[m- 1][j] == 'O')
                backtrace(board, m-1, j, offsets);            
        }
        // 替換內部的O
        for ( int i = 0;i< m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        // 將邊界的o換回O
        for ( int i = 0;i< m; i++){
            for (int j = 0; j < n; j++){
                if (board[i][j] == 'o')
                    board[i][j] = 'O';
            }
        }
    }

    void backtrace(vector<vector<char>>& board, int x, int y, vector<pair<int, int>>& offsets){
        board[x][y] = 'o';
        for (auto off: offsets ){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (! inboard(board, new_x, new_y) || board[new_x][new_y] != 'O') continue;
            backtrace(board, new_x, new_y, offsets);
        }
    }

    bool inboard(vector<vector<char>>& board, int x, int y){
        return (x >= 0 && x < board.size()) && ( y >= 0 && y < board[0].size());
    }
};

417 太平洋大西洋水流問題（medium)

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        //使用兩個數組分別表示能流到大西洋atlantic與太平洋pacific的位置
        if (matrix.empty()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        vector<vector<bool>> pacific(m, vector<bool>(n, false));

        vector<pair<int, int>> offsets({ {-1, 0},{0, -1},{1, 0},{0, 1}});
        vector<vector<int>> res;

        for (int i  = 0; i< m; i++){
            if (! pacific[i][0])
                backtrace(matrix, i, 0, pacific, offsets);
            if (! atlantic[i][n-1])
                backtrace(matrix, i, n-1, atlantic, offsets);
        }
        for (int j  = 0; j< n; j++){
            if (! pacific[0][j])
                backtrace(matrix, 0, j, pacific, offsets);
            if (! atlantic[m-1][j])
                backtrace(matrix, m-1, j, atlantic, offsets);
        }
        for (int i =0; i<m; i++){
            for (int j = 0; j<n; j++){
                if (atlantic[i][j] && pacific[i][j])
                    res.push_back({i, j});
            }
        }
        return res;
    }
    
    void backtrace(vector<vector<int>>& matrix, int x, int y, vector<vector<bool>>& ocean, vector<pair<int, int>>& offsets){
        ocean[x][y] = true;
        for (auto off: offsets){
            int new_x = x + off.first;
            int new_y = y + off.second;
            if (!inboard(matrix, new_x, new_y) || matrix[new_x][new_y] < matrix[x][y] || ocean[new_x][new_y]) continue;
            backtrace(matrix, new_x, new_y, ocean, offsets);
        }
    }

    bool inboard(vector<vector<int>>& matrix, int x, int y){
        return (x >= 0 && x < matrix.size()) && ( y >= 0 && y < matrix[0].size());
    }
};

51 N皇后（hard）

class Solution {
public:
    vector<vector<string>> queues;
    vector<vector<string>> solveNQueens(int n) {
        //主對角線i- j為常數，範圍為1-n到n-1
        // 副對角線i+j為常數，範圍為0到2*n-2
        vector<int> diag(2*n-1, false); //主對角線，i - j + n - 1為其索引對應的對角線
        vector<int> otherdiag(2*n-1, false); // 副對角線i + j 為其索引對應的對角線。
        vector<int> queue(n, -1); //表示每行放置在哪一列。
        unordered_set<int> cols;  // 表示已經放置的列


        backtrace(n, diag, otherdiag, queue, cols, 0);

        return queues; 

    }
    void backtrace(int n, vector<int>& diag, vector<int>& otherdiag, vector<int>& queue, unordered_set<int> cols, int row){
        if (row == n){
            queues.push_back(generateString(queue, n));
            return ;
        }
        for (int j = 0; j < n; j++){
            if (diag[row-j+n-1] || otherdiag[row+j] || cols.find(j) != cols.end()) continue;
            diag[row-j+n-1] = true;
            otherdiag[row+j] = true;
            cols.insert(j);
            queue[row] = j;
            backtrace(n, diag, otherdiag, queue, cols, row + 1);
            diag[row-j+n-1] = false;
            otherdiag[row+j] = false;
            queue[row] = -1;
            cols.erase(j);
        }
    }
    vector<string> generateString(vector<int>& queue, int n){
        vector<string> res(n, string(n, '.'));

        for (int i=0; i< n; i++)
            res[i][queue[i]] = 'Q';

        return res;
    }
};

52 N皇后 II（hard）

class Solution {
public:
    int totalNQueens(int n) {
        vector<bool> diag(2*n - 1, false); // 主對角線是否佔用， i-j+n-1為其主對角線的索引
        vector<bool> otherdiag(2*n-1, false); //副對角線，i+j為其索引
        unordered_set<int> cols; // 保存已經被佔用的列
        vector<int> queue(n, -1); //表示每個元素分別放置在第j列的位置。
        int res = 0;
        backtrace(n, diag, otherdiag, cols, queue, res, 0);
        return res;
    }
    void backtrace(int n, vector<bool>& diag, vector<bool>& otherdiag, unordered_set<int>& cols, vector<int>& queue, int& res, int row){
        if (row == n){
            res++;
            return ;
        }
        // 第row行可以放的列的位置，遍歷查找
        for (int i=0; i< n; i++){
            if(diag[row - i + n - 1] || otherdiag[row + i] || cols.find(i) != cols.end()) continue;
            diag[row - i + n - 1 ] = true;
            otherdiag[row + i] = true;
            cols.insert(i);
            queue[row] = i;
            backtrace(n, diag, otherdiag, cols, queue, res, row+1);
            diag[row - i + n - 1 ] = false;
            otherdiag[row + i] = false;
            cols.erase(i);
            queue[row] = -1;           
        }
    }
};

37 解數獨（hard）

class Solution {
public:
    bool valid = false;
    void solveSudoku(vector<vector<char>>& board) {
        vector<unordered_set<int>> rows(9, unordered_set<int>()); //每行出現過的數字
        vector<unordered_set<int>> cols(9, unordered_set<int>()); //每列出現過的數字
        vector< unordered_set<int> > grids(9, unordered_set<int>()); // 第i個3x3的格子出現過的數字，其索引為（i/3）*3 + j/3
        vector<pair<int, int>> spaces;
        for ( int i = 0; i <9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] == '.')
                    spaces.push_back(make_pair(i, j));
                else{
                    int digit = int(board[i][j] - '0');
                    rows[i].insert(digit);
                    cols[j].insert(digit);
                    grids[(i/3)*3+j/3].insert(digit);
                }
            }
        }
        backtrace(board, rows, cols, grids, spaces, 0);
        return;
    }
    void backtrace(vector<vector<char>>& board, vector<unordered_set<int>>& rows, vector<unordered_set<int>>& cols, vector<unordered_set<int>>& grids, vector<pair<int, int>>& spaces, int index){
        if ( index == spaces.size()) {
            valid = true;
            return ;
        }
        int i = spaces[index].first;
        int j = spaces[index].second;
        // 放置 k 這個數字
        for (int k = 1; k <= 9; k++){
            if (valid) break;
            if ( rows[i].find(k) != rows[i].end() || cols[j].find(k) != cols[j].end() || grids[(i/3)*3+j/3] .find(k) != grids[(i/3)*3+j/3].end() ) 
                continue;
            rows[i].insert(k);
            cols[j].insert(k);
            grids[(i/3)*3+j/3].insert(k);
            board[i][j] = (char) ('0' + k);
            backtrace(board, rows, cols, grids, spaces, index+1);
            rows[i].erase(k);
            cols[j].erase(k);
            grids[(i/3)*3+j/3].erase(k);
            // board[i][j] = '.';
        }
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn部落格： //blog.csdn.net/lxztju

• 知乎專欄： 小哲AI

• AI研習社專欄：小哲AI