大家好，最近一直在写算法，刷了力扣中部分回溯，总结了大致题型和思路，在这里分享给大家，希望大家可以有所收获！！！

目录

回溯算法的基本思想：

回溯的典型结构：

算法思路讲解：

1. 组合

2.子集：

3.全排列：

4.N皇后：

---

什么是回溯？？？

回溯就是一种通过递归解决问题的算法思想，这种方法适用于那些需要穷举所有可能的复杂问题，比如排列，组合，子集，棋盘等，因为回溯是通过递归实现的，所以回溯理解起来也比较困难，并且在时间复杂度上也比较高，它的复杂度通常是指数级别 O(2^n) 或 阶乘级别 O(n!)。虽然可以通过剪枝来减少搜索空间，但总体而言，回溯在大规模问题上效率不高

回溯算法的基本思想：

回溯算法的核心思想：尝试所有的可能，当发现某一解不符合时，就进行回退到上一步，然后选择其他路径，直到遍历所有可能

回溯的典型结构：

以递归的形式出现，每一步尝试都会进入递归分支，直到找到合适的解或者发现需要回退

void backtrack(参数) {if (满足结束条件) {// 找到解return;}for (所有可能的选择) {做出选择;递归调用 backtrack(新的参数);撤销选择（回溯）;}
}

算法思路讲解：

1. 组合

题目链接：77. 组合 - 力扣（LeetCode）

给定两个整数n和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。 

示例 1：

输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

解释：找[1,4]范围内的数中两个数的组合

定义一个全局result，将它当做参数进行传递，然后通过遍历将解添加到result当中，然后进行返回 

思路：

因为我们返回的是一个一个二维容器，所以我们需要一维容器进行填充，因此我们主要操作的是一维容器而不是二维容器，二维是我们一维在符合条件时进行添加的

详细代码流程：

ans=[ ]不符合条件，进入第一个for循环，startIndex=1，将 i 添加到ans中，进入getResult()当中

ans=[ 1 ]不符合条件，进入第二个for循环，startIndex=2，将2进行添加上去,进入getResult()当中

ans=[ 1,2 ]符合条件，将ans添加到result当中，返回第二个for循环的getResult()位置，然后进行尾删，删除2，i+1=3，将3添加到ans当中，进入getResult()当中

ans=[ 1,3 ]符合条件，将ans添加到result当中，回到第二个for循环的getResult()位置，然后进行尾删，删除3，i+1=4，将4添加到ans当中，进入getResult()当中

ans=[ 1,4 ]符合条件，将ans添加到result当中，回到第二个for循环的getResult()位置，然后进行尾删，删除4，第二个for循环循环完毕，回到第一个for循环的getResult()位置，然后进行尾删，i+1=2,添加2，ans=[2],然后进入到getResult()当中，ans不符合条件，开始第三for循环......(同上)

                         []/   |   |   \[1]    [2]  [3]  [4]/   \     |    |[1,2] [1,3]  [2,3] [3,4]|     |      |[1,4]  [1,4]  [2,4]

 大家可以结合上面的两个，相信已经表明的很清楚了

class Solution {vector<vector<int>> result;vector<int> ans;public:void getResult(int n, int k, int startIndex) {if (ans.size() == k) {result.push_back(ans);return;}for (int i = startIndex; i <= n - (k - ans.size()) + 1; i++) {ans.push_back(i);getResult(n, k, i + 1);ans.pop_back();}}public:vector<vector<int>> combine(int n, int k) {getResult(n, k, 1);return result;}
};

 以下是关于 i <= n - (k - ans.size()) + 1的剪枝操作

1. 已经选择的元素个数：path.size();
2. 所需需要的元素个数为: k - path.size();
3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
5. 为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
6. 举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
7. 从2开始搜索都是合理的，可以是组合[2, 3, 4]。

2.子集：

题目链接：78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 

示例 1：

输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 子集思路和组合相似，这里就不详细讲解，下面是实现流程

                              [ ]/     |    \[1]       [2]    [3]/    \     /   \  [1,2]  [1,3] [2,3] [2]    /                [1,2,3]          

void getResult(vector<int>& nums, int startIndex) {if (startIndex<=nums.size()) {result.push_back(ans);}for (int i = startIndex; i < nums.size(); i++) {ans.push_back(nums[i]);getResult(nums, i + 1);ans.pop_back();}}

3.全排列：

题目链接：46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 

示例 1：

输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 

                          [1, 2, 3]/          |          \[1, 2, 3]        [1, 3, 2]         [2, 1, 3]|                  |               |/       \          /      \         /      \
[1, 2, 3] [1, 3, 2]  [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

 void getResult(vector<int>& nums, int startIndex) {if (startIndex == nums.size()) {result.push_back(nums);return;}for (int i = startIndex; i < nums.size(); i++) {swap(nums[startIndex], nums[i]);getResult(nums, startIndex + 1);swap(nums[startIndex], nums[i]);}}

4.N皇后：

题目链接：51. N 皇后 - 力扣（LeetCode）

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 

示例 1：

输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。

初始状态:

[ . . . . ]

[ . . . . ]

[ . . . . ]

[ . . . .

第一层递归 (row = 0)： - 尝试在第 0 行的每一列放置皇后。 - 选择在 (0, 0) 放置 Q。

[ Q . . . ]

[ . . . . ]

[ . . . . ]

[ . . . . ]

第二层递归 (row = 1)： - 尝试在第 1 行的每一列放置皇后。 - 选择在 (1, 2) 放置 Q。（下面for循环中有一个判断，如果不符合条件就不会执行自身函数  所以Q才会直接到第三个）

[ Q . . . ]

[ . . Q . ]

[ . . . . ]

[ . . . . ]

第三层递归 (row = 2)： - 尝试在第 2 行的每一列放置皇后。 - 选择在 (2, 1) 放置 Q。

[ Q . . . ]

[ . . Q . ]

[ . Q . . ]

[ . . . . ]

第四层递归 (row = 3)： - 尝试在第 3 行的每一列放置皇后。 - 选择在 (3, 3) 放置 Q，找到一个解。

[ Q . . . ]

[ . . Q . ]

[ . Q . . ]

[ . . . Q ]

回溯到第三层，尝试其他列放置皇后： - 尝试在 (2, 2)，发现冲突，回溯到第二层。 回溯到第二层，尝试其他列放置皇后： - 尝试在 (1, 3)，发现冲突，回溯到第一层。 回溯到第一层，尝试其他列放置皇后： - 尝试在 (0, 1) 放置 Q。

[ . Q . . ]

[ . . . . ]

[ . . . . ]

[ . . . . ] - 接着重复这个过程，直到探索完所有可能。

class Solution {vector<vector<string>> ans;public:void getAns(int n, int row, vector<string>& chessboard) {if (row == n) {ans.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isKingdom(row, col, n, chessboard)) {chessboard[row][col] = 'Q';getAns(n, row + 1, chessboard);chessboard[row][col] = '.';}}}bool isKingdom(int row, int col, int n, vector<string>& chessboard) {// 检查列for (int i = 0; i < row; i++) { // 这是一个剪枝if (chessboard[i][col] == 'Q') {return false;}}// 检查 45度角是否有皇后for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') {return false;}}// 检查 135度角是否有皇后for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;}public:vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));getAns(n, 0, chessboard);return ans;}
};

 到这里讲解完了，感谢大家观看，给个免费的赞叭！！！