一. 回溯法

回溯也叫回溯搜索法，它是搜索的一种方式，用来解决可以抽象为树形结构的问题。回溯是递归的副产品，只要由递归就会有回溯。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。

回溯法并不高效，但有些问题只能通过回溯暴力搜索求解：

1. 组合问题：N 个数里按一定规则找出 K 个数的集合，不强调元素顺序
2. 子集问题：一个 N 个数的集合有多少符合条件的子集
3. 排列问题：N 个数按一定规则全排列，有几种排列方式，强调元素顺序
4. 棋盘问题：N 皇后，解数独等

1.1 组合问题

给定两个整数 n 和 k，返回 1…n 中所有可能的 k 个数的集合

template<typename T>
std::ostream &operator<<(std::ostream &os, std::vector<std::vector<T>> vector){
    os << '{';
    for(int i = 0; i < vector.size(); ++i){
        os << '{'; 
        for(int j = 0; j < vector[i].size(); ++j){
            os << vector[i][j];
            if(j != vector[i].size() - 1)
                os << ", ";
        }
        os << "}";
        if(i != vector.size() - 1)
            os << ", ";
    }
    os << "}";
    return os;
}

class Solution{
public:
    std::vector<std::vector<int>> combine(int n, int k){
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        auto inner = [&result, &path, n, k](const auto &inner, int start) -> void{
            if(path.size() == k){
                result.emplace_back(path);
                return;
            }
            for(int i = start; i <= n - (k - path.size()) + 1; ++i){
                path.emplace_back(i);
                inner(inner, i + 1);
                path.pop_back();
            }
        };
        inner(inner, 1);
        return result;
    }
};

剪枝优化

1.2 子集问题

组合问题可以认为是找出树形结构的叶子节点，子集问题可以认为是找出树形结构的所有节点

class Solution{
public:
    std::vector<std::vector<int>> subsets(const std::vector<int> &nums){
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        auto inner = [&result, &path, &nums](const auto &inner, int start) -> void{
            result.emplace_back(path);
            for(int i = start; i < nums.size(); ++i){
                path.emplace_back(nums[i]);
                inner(inner, i + 1);
                path.pop_back();
            }
        };
        inner(inner, 0);
        return result;
    }
};

1.3 排列问题

给定一个没有重复数字的序列，返回其所有可能的全排列

排列是有序的，即 {1， 2} 和 {2， 1} 是两个集合，这与组合问题，子集问题是不同的

需要使用 used 数组记录此时 path 里都有哪些元素使用了，一个排列里元素只能使用一次

class Solution{
public:
    std::vector<std::vector<int>> permutation(const std::vector<int> &nums){
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        std::vector<bool> used(nums.size(), false);
        auto inner = [&result, &path, &nums, &used](const auto &inner) -> void{
            if(path.size() == nums.size()){
                result.emplace_back(path);
                return;
            }
            for(int i = 0; i < nums.size(); ++i){
                if(used[i])
                    continue;
                used[i] = true;
                path.emplace_back(nums[i]);
                inner(inner);
                path.pop_back();
                used[i] = false;
            }
        };
        inner(inner);
        return result;
    }
};

1.4 N 皇后问题

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

std::ostream &operator<<(std::ostream &os, std::vector<std::vector<std::string>> vector){
    for(int i = 0; i < vector.size(); ++i){
        for(int j = 0; j < vector[i].size(); ++j){
            os << vector[i][j];
            if(j != vector[i].size() - 1)
                os << '\n';
        }
        if(i != vector.size() - 1)
            os << "\n==================================\n";
    }
    return os;
}

class Solution{
public:
    std::vector<std::vector<std::string>> NQueens(int N){
        auto is_valid = [N](std::vector<std::string> chess_board, int row, int col){
            for(int i = 0; i < row; ++i)
                if(chess_board[i][col] == 'Q')
                    return false;
            for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
                if(chess_board[i][j] == 'Q')
                    return false;
            for(int i = row - 1, j = col + 1; i >= 0 && j < N; --i, ++j)
                if(chess_board[i][j] == 'Q')
                    return false;
            return true;
        };

        std::vector<std::vector<std::string>> result;
        std::vector<std::string> chess_board(N, std::string(N, '.'));
        auto inner = [&result, &chess_board, &is_valid, N](const auto &inner, int row) -> void{
            if(row == N){
                result.emplace_back(chess_board);
                return;
            }
            for(int col = 0; col < N; ++col){
                if(is_valid(chess_board, row, col)){
                    chess_board[row][col] = 'Q';
                    inner(inner, row + 1);
                    chess_board[row][col] = '.';
                }
            }
        };
        inner(inner, 0);
        return result;
    }
};