剑指offer：递归（回溯）
BM55 没有重复项数字的全排列
题目
题解(98)
讨论(161)
排行
面经new
中等 通过率：56.95% 时间限制：1秒 空间限制：256M
知识点
递归
描述
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
数据范围：数字个数 0 < n \\le 60<n≤6
要求：空间复杂度 O(n!)O(n!) ，时间复杂度 O(n!）O(n!）
示例1
输入：
[1,2,3]
复制
返回值：
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
复制
示例2
输入：
[1]
复制
返回值：
[[1]]
复制
class Solution {
public:void recursion(vector<vector<int> > &res, vector<int> &num, int index){if (index == num.size() - 1) {res.push_back(num);return;}for(int i = index; i < num.size(); i++) { swap(num[i], num[index]);recursion(res, num, index + 1); swap(num[i], num[index]);}}vector<vector<int> > permute(vector<int> &num) {//先按字典序排序sort(num.begin(), num.end()); vector<vector<int> > res;recursion(res, num, 0); return res;}
};
BM56 有重复项数字的全排列（这个题目是数组，和下一个题目字符串是相同的方法）
题目
题解(92)
讨论(158)
排行
面经new
中等 通过率：39.45% 时间限制：1秒 空间限制：256M
知识点
递归
描述
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
数据范围： 0 < n \\le 80<n≤8 ，数组中的值满足 -1 \\le val \\le 5−1≤val≤5
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
示例1
输入：
[1,1,2]
复制
返回值：
[[1,1,2],[1,2,1],[2,1,1]]
复制
示例2
输入：
[0,1]
复制
返回值：
[[0,1],[1,0]]
复制
class Solution {
public:void recursion(vector<int> &num, vector<int> &used){//临时字符串满足条件放入字符串数组if(temp.size() == num.size()) {vec.push_back(temp);return;}//遍历所有元素，选取一个元素加入临时字符串tempfor(int i = 0; i < num.size(); ++i) {//如果该元素已经被加入临时字符串temp，继续遍历if(used[i] == 1) {continue;}//当前的元素str[i]和前一个元素str[i-1]相同，并且前一个元素str[i-1]已经用过，继续遍历if(i > 0 && num[i-1] == num[i] && 1 == used[i-1]) {continue;}//加入临时字符串temp.push_back(num[i]);//标记为使用过 used[i] = 1; //递归遍历recursion(num, used);//从临时字符串去除temp.pop_back();//标记为未使用used[i] = 0;}}vector<vector<int> > permuteUnique(vector<int>& num) {//先按字典序排序，使重复字符串相邻sort(num.begin(), num.end());//标记每个位置的字符是否被使用过//0表示未使用过，1表示使用过vector<int> used(num.size(), 0);//递归获取recursion(num, used);//返回结果return vec;}
private:vector<vector<int>> vec;vector<int> temp;
};
JZ38 字符串的排列（这个题目是字符串，和上一个题目数组是相同的方法）
中等 通过率：23.80% 时间限制：1秒 空间限制：256M
知识点字符串递归
描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
示例1
输入：
“ab”
返回值：
[“ab”,“ba”]
说明：
返回[“ba”,“ab”]也是正确的
示例2
输入：
“aab”
返回值：
[“aab”,“aba”,“baa”]
示例3
输入：
“abc”
返回值：
[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
示例4
输入：
“”
返回值：
[“”]
关联企业
class Solution {
public:void recursion(string &str, vector<int> &used){//临时字符串满足条件放入字符串数组if(temp.size() == str.length()) {vec.push_back(temp);return;}//遍历所有元素，选取一个元素加入临时字符串tempfor(int i = 0; i < str.length(); ++i) {//如果该元素已经被加入临时字符串temp，继续遍历if(used[i] == 1) {continue;}//当前的元素str[i]和前一个元素str[i-1]相同，并且前一个元素str[i-1]已经用过，继续遍历if(i > 0 && str[i-1] == str[i] && 1 == used[i-1]) {continue;}//加入临时字符串temp.push_back(str[i]);//标记为使用过 used[i] = 1; //递归遍历recursion(str, used);//从临时字符串去除temp.pop_back();//标记为未使用used[i] = 0;}}vector<string> Permutation(string str) {//先按字典序排序，使重复字符串相邻sort(str.begin(), str.end());//标记每个位置的字符是否被使用过//0表示未使用过，1表示使用过vector<int> used(str.size(), 0);//递归获取recursion(str, used);//返回结果return vec;}
private:vector<string> vec;string temp;
};
BM57 岛屿数量
题目
题解(135)
讨论(187)
排行
面经new
中等 通过率：41.25% 时间限制：1秒 空间限制：256M
知识点
dfs
广度优先搜索(BFS)
搜索
描述
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
(注：存储的01数据其实是字符’0’,‘1’)
示例1
输入：
[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
复制
返回值：
3
复制
示例2
输入：
[[0]]
复制
返回值：
0
复制
示例3
输入：
[[1,1],[1,1]]
复制
返回值：
1
复制
备注：
01矩阵范围<=200*200
方法一：深度优先搜索dfs
知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。
思路：
矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs）：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，因此可以用递归实现。
123456789 //后续四个方向遍历if(i - 1 >= 0 && grid[i - 1][j] == ‘1’) dfs(grid, i - 1, j);if(i + 1 < n && grid[i + 1][j] == ‘1’) dfs(grid, i + 1,j);if(j - 1 >= 0 && grid[i][j - 1] == ‘1’) dfs(grid, i, j - 1);if(j + 1 < m && grid[i][j + 1] == ‘1’) dfs(grid, i, j + 1);
终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。
返回值： 每一级的子问题就是把修改后的矩阵返回，因为其是函数引用，也不用管。
本级任务： 对于每一级任务就是将该位置的元素置为0，然后查询与之相邻的四个方向，看看能不能进入子问题。
具体做法：
step 1：优先判断空矩阵等情况。
step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
step 3：接着将该位置的1改为0，然后使用dfs判断四个方向是否为1，分别进入4个分支继续修改。
class Solution {
public:/*** 判断岛屿数量* @param grid char字符型vector<vector<>> * @return int整型*/int solve(vector<vector<char> >& grid) {if (grid.empty()) {return 0;}int row = grid.size();int col = grid[0].size();int num = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == '1') {num++;dfs(grid, i, j);}}}return num;}void dfs(vector<vector<char>>& grid, int i, int j){int row = grid.size();int col = grid[0].size();grid[i][j] = '0';if (i-1 >= 0 && grid[i-1][j] == '1') {dfs(grid, i-1, j);}if (i+1 < row && grid[i+1][j] == '1') {dfs(grid, i+1, j);}if (j-1 >= 0 && grid[i][j-1] == '1') {dfs(grid, i, j-1);}if (j+1 < col && grid[i][j+1] == '1') {dfs(grid, i, j+1);}}
};
方法二：广度优先搜索bfs
知识点：广度优先搜索（bfs）
广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再往更深处，进入与其他节点直接相连的节点。bfs的时候我们常常会借助队列的先进先出，因为从某个节点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再将与它们直接相连的节点加入，由此就可以依次按层访问。
思路：
统计岛屿的方法可以和方法一同样遍历解决，为了去重我们还是要将所有相邻的1一起改成0，这时候同样遍历连通的广度优先搜索（bfs）可以代替dfs。
具体做法：
step 1：优先判断空矩阵等情况。
step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
step 3：使用bfs将遍历矩阵遇到的1以及相邻的1全部置为0：利用两个队列辅助（C++可以使用pair），每次队列进入第一个进入的1，然后遍历队列，依次探讨队首的四个方向，是否符合，如果符合则置为0，且位置坐标加入队列，继续遍历，直到队列为空。
class Solution {
public:/*** 判断岛屿数量* @param grid char字符型vector<vector<>> * @return int整型*/int solve(vector<vector<char> >& grid) {if (grid.empty()) {return 0;}int row = grid.size();int col = grid[0].size();int num = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == '1') {num++;grid[i][j] = '0';queue<pair<int, int>> que;que.push({i, j});while (!que.empty()) {auto temp = que.front();que.pop();int x = temp.first;int y = temp.second;if (x-1 >= 0 && grid[x-1][y] == '1') {que.push({x-1, y});grid[x-1][y] = '0';}if (x+1 < row && grid[x+1][y] == '1') {que.push({x+1, y});grid[x+1][y] = '0';}if (y-1 >= 0 && grid[x][y-1] == '1') {que.push({x, y-1});grid[x][y-1] = '0';}if (y+1 < col && grid[x][y+1] == '1') {que.push({x, y+1});grid[x][y+1] = '0';}}}}}return num;}
};
BM60 括号生成
中等 通过率：54.31% 时间限制：1秒 空间限制：256M
知识点递归
描述
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
“((()))”, “(()())”, “(())()”, “()()()”, “()(())”
数据范围：0≤n≤10
要求：空间复杂度 O(n)，时间复杂度 O(2n)
示例1
输入：
1
返回值：
[“()”]
示例2
输入：
2
返回值：
[“(())”,“()()”]
class Solution {
public:void recursion(int left, int right, string temp, vector<string>& res, int n){//左右括号都用完了，就加入结果if(left == n && right == n){ res.push_back(temp);return;}//使用一次左括号if(left < n) {recursion(left + 1, right, temp + "(", res, n);}//使用右括号个数必须少于左括号if(right < n && left > right) {recursion(left, right + 1, temp + ")", res, n);}}vector<string> generateParenthesis(int n) {//记录结果vector<string> res;//记录每次组装的字符串string temp; //递归recursion(0, 0, temp, res, n); return res;}
};