回溯

August 10, 2023

回溯

回溯算法相当于 DFS

cpp

// 二叉树
void traverse(TreeNode *root)
{
    if (!root) return;

    // 前序遍历代码写在这里
    traverse(root->right);
    // 中序遍历代码写在这里
    traverse(root->left);
    // 后序遍历代码写在这里
}

// N叉树
void traverse(TreeNode *root)
{
    if (!root) return;

    for (auto child : root->children)
    {
        // 前序遍历代码写在这里
        traverse(child);
        // 后序遍历代码写在这里
    }
}

回溯伪代码如下

def backtrace(choiceList, track, answer):
    if ok(track):
        answer.append(track)
        return

    for choice in choiceList:
        # choose:   选择一个 choice 加入 track
        backtrace(choiceList, track, answer)  # 做下一个选择
        # unchoose: 从 track 中撤销上面的选择

可以发现，回溯相当于 N 叉树的遍历

举例：最简单的回溯问题

描述：
给定一个没有重复数字的整数数组 nums 和一个整数 n，要求返回所有可能的 n 元组，其中每个元素都可以在 nums 中任意选择。

示例：
假设给定数组 nums = [1, 2, 3]，整数 n = 2，则所有可能的 2 元组为：

[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
private:
    vector<vector<int>> answer;

    vector<int> track;

    void backtrace(vector<int> &nums, int n)
    {
        if (track.size() == n) // 终止条件
        {
            answer.push_back(track); // 提交结果
            return;
        }

        for (int i = 0; i < nums.size(); i++) // 遍历当前层所有可能项
        {
            track.push_back(nums[i]); // 生成当前项
            backtrace(nums, n);       // 生成下一项
            track.pop_back();         // 回溯，撤销当前项
        }
    }

public:
    vector<vector<int>> permute(vector<int> &nums, int n)
    {
        backtrace(nums, n);
        return answer;
    }
};

/**
 * 测试，可忽略
 */
int main()
{
    Solution test;
    vector<int> nums{1, 2, 3};
    vector<vector<int>> result = test.permute(nums, 2);

    for (auto vec : result)
    {
        cout << "[";
        for (auto n : vec)
        {
            cout << n;
            cout << ", ";
        }
        cout << "]" << endl;
    }
}

注意观察输出结果的顺序。

上面的问题中，时间复杂度是 O(n^k) ，也就是要做 k 次循环
由于 k 是变量，我们无法通过编写 k 个 for 循环实现
而是要通过栈实现

N 皇后问题

leetcode 描述：https://leetcode.cn/problems/n-queens/

朴素观点来看，N 皇后问题其实是时间复杂度为 O(n^n) 的回溯问题
合理剪枝可降低时间复杂度

cpp

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
private:
    vector<vector<string>> answer;
    void backtrace(int n, int row, vector<string> &board)
    {
        if (row >= n)
        {
            answer.push_back(board);
            return;
        }

        // evaluate board[row][col]
        for (int col = 0; col < n; col++)
        {
            // 注意：我们只放Q，不放.
            if (isValid(n, row, col, board))
            {
                board[row][col] = 'Q';        // 放置
                backtrace(n, row + 1, board); // 下一行 （同一行只能一个Q）
                board[row][col] = '.';        // 撤销
            }
            else
            {
                continue;
                // 相当于：
                // board[row][col] = '.';
            }
        }
    }

    bool isValid(int n, int row, int col, vector<string> &board)
    {
        // _|_
        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 >= 0; i--, j--)
        {
            if (board[i][j] == 'Q')
                return false;
        }
        // _/_
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (board[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> board(n, string(n, '.'));
        backtrace(n, 0, board);
        return answer;
    }
};

/**
 * 测试，可忽略
 */
int main()
{
    int n = 4;
    Solution solution;
    vector<vector<string>> result = solution.solveNQueens(n);

    for (auto &res : result)
    {
        for (auto &row : res)
        {
            cout << row << endl;
        }
        cout << endl;
    }
}

解数独

leetcode 描述：https://leetcode.cn/problems/sudoku-solver/submissions/

数独问题和 N 皇后问题如出一辙

cpp

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
private:
    bool backtrace(vector<vector<char>> &board)
    {
        for (int row = 0; row < 9; row++)
            for (int col = 0; col < 9; col++)
            {
                // 不是空白处不用放
                if (board[row][col] != '.')
                    continue;

                // 两层 for 遍历行和列，再一层 for 遍历所有可能的选择
                for (char n = '1'; n <= '9'; n++)
                    if (isValid(board, row, col, n))
                    {
                        board[row][col] = n;

                        if (backtrace(board)) // 由于已经放置了当前位置，下一次递归就会继续去下一个位置
                            return true;      // 如果之后的位置也是都可以放置，那么就直接返回
                        else                  // 如果后面的位置有不可以放的，就回溯
                            board[row][col] = '.';
                    }

                return false; // 当前位置都不可以放，直接返回（回溯）
            }
        // 已解完
        return true;
    }

    bool isValid(vector<vector<char>> &board, int row, int col, char n)
    {
        // 注意这里直接检查整行和整列，而不是只检查之前行和列
        // 否则也可以通过但是会超时（想想为什么？）

        // -
        for (int j = 0; j < 9; j++)
            if (board[row][j] == n)
                return false;

        // |
        for (int i = 0; i < 9; i++)
            if (board[i][col] == n)
                return false;

        // 3*3
        int x = row - (row % 3);
        int y = col - (col % 3);
        for (int i = x; i < x + 3; i++)
            for (int j = y; j < y + 3; j++)
                if (board[i][j] == n)
                    return false;

        // ok
        return true;
    }

public:
    void
    solveSudoku(vector<vector<char>> &board)
    {
        backtrace(board);
    }
};

/**
 * 测试，可忽略
 */
int main()
{
    vector<vector<char>> board = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

    cout << "Original:" << endl;
    for (const auto &row : board)
        for (char ch : row)
            cout << ch << " ";
    cout << endl;

    Solution solution;
    solution.solveSudoku(board);

    cout << "Solved:" << endl;
    for (const auto &row : board)
        for (char ch : row)
            cout << ch << " ";
    cout << endl;
}

←Back to home