回溯思想

回溯可以认为是一种使用递归的暴力，通过不断地试验与回溯寻找正确答案。

核心：

• 采取递归的形式，从目前的状态向下一满足条件的状态递归，若不满足，则撤销本次操作，返回上一状态。

工作原理：

• 状态空间树: 问题的所有可能解可以表示为一棵树，回溯算法就是在这棵树上进行深度优先遍历。也可以理解为栈数组，通过不断地push与pop操作处理。
• 递归与回溯: 在尝试下一步选择前，当前状态需要被保存，若当前选择不合适，则“回溯”到之前的状态继续尝试其他选择。

典型问题

N皇后问题

在一个N×N的棋盘上，放置N个皇后，使得任何两个皇后都不能在同一行、同一列或同一对角线上。

简单解释为：目前为空，我要在第一列放置，1号位合理。接下来要在第二列放置，1号位冲突，2号位冲突，3号位合理，进入下一列。若当前所有位置都冲突，意味着上一个选择为错误，则返回上一列，选择下一个位置。 代码示例：

class Solution
{
public:
    int totalNQueens(int n)
    {
        vector<int> queens(n, -1);
        int res = 0;
        dfs(queens, 0, res);//从初始空状态开始
        return res;
    }
    void dfs(vector<int> &queens, int row, int &res)
    {
        if (row == queens.size()) // 当前排满，为答案
        {
            res++;
            return; // 返回上一状态
        }
        for (int i = 0; i < queens.size(); i++)
        {
            if (isSafe(queens, row, i))//可以加入，满足条件
            {
                queens[row] = i;
                dfs(queens, row + 1, res);
                queens[row] = -1;
            }
        }
        //return; 执行到这儿，要么不满足条件，要么满足条件的已被遍历。
    }
    bool isSafe(vector<int> &queens, int row, int col)//是否符合题意。
    {
        for (int i = 0; i < row; i++)
        {
            if (queens[i] == col || abs(queens[i] - col) == abs(i - row))
                return false;
        }
        return true;
    }
};

子集问题

给你一个整数数组 nums ，其中没有重复元素，请你返回该数组所有可能的子集。

简单来说就是每个数有两种可能，选择与不选择。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(0, nums, current, result);
        return result;
    }
private:
    void backtrack(int start, vector<int>& nums, vector<int>& current, vector<vector<int>>& result) {
        // 将当前子集加入结果集中
        result.push_back(current);
        // 从当前位置开始，递归构建子集
        for (int i = start; i < nums.size(); i++) {
            // 做出选择：将nums[i]加入当前子集
            current.push_back(nums[i]);
            // 递归调用，继续构建子集
            backtrack(i + 1, nums, current, result);
            // 撤销选择，回溯
            current.pop_back();
        }
    }
};

在这个代码中，选择当前数字后，进行组合，或者不选择当前数字，直接将下个数字设为”初始状态“，依次来遍历所有情况。

回溯的优化

事实上，回溯与暴力相同，可以认为是暴力的一种。例如在N皇后中，回溯实际上就是遍历所有可能得情况，得到所有的正确答案。正如前面所说，回溯过程可以看作DFS一个N叉树。 那么核心优化点为剪枝： 在递归过程中，可以提前终止一些不可能成功的分支，以减少计算量。例如在N皇后问题中，如果当前列已经有皇后，则无需继续递归。