代码随想录算法训练营第60期第二十九天打卡

       今天我们接着昨天的回溯算法继续我们今天的题目，今天应该是回溯算法的最后一个章节，今天有几道比较难的题目，一个是N皇后，另一个是解数独，这俩我N皇后打蓝桥杯的时候是学过的，所以这个我会给大家讲一下，解数独我尽力而为，今天的全排列问题是重点，其实与我们前面的组合问题和子集问题是相类似的，我们就开始今天的题目。

第一题对应力扣编号为491的题目非递减子序列

        这道题由于我了解过动态规划，动态规划里面就有求最长上升子序列的思路以及状态转移，但是这里我们处在回溯算法章节自然还是会考虑回溯算法解决，我们一起来看一下：

        注意我们求出的非递减序列是不可以改变原数组元素的相对位置的，相等的元素也是可以的，我们尝试使用回溯算法来解决一下：

       我们来看一下这幅图，这里其实给我们展示了寻找非递减子序列的过程，首先我们要知道我们在同一个父节点之下是不可以使用相同的元素的，如果使用了相同的元素，如图所示就会出现重复的子序列，我们后面的代码里面的集合其实就是保存同一父节点的元素，保证同一父节点下不会重复使用一个元素，这就是本题的难点所在，也是陷阱所在，大家注意理解。

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(const vector<int>&nums, int startIndex){//递归的终止条件不过这里似乎与以前的递归终止条件不太一样//我们这里为啥没有return因为我们取的是树上的节点而且要多次取if (path.size() > 1) result.push_back(path);unordered_set<int> uset;//注意我们取非递减子序列的时候我们每一个元素都是只能使用一次的所以这里我们涉及到了去重操作//理解这一段代码很重要我们什么情况下是不符合条件的  第一种就是不满足非单调递减 第二种就是重复出现过的元素for (int i = startIndex; i < nums.size(); ++i){if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue;uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

        这里我们使用到了set去重，上面解释过了我们避免出现相同子序列的逻辑，这样我们继续我们的递归与回溯操作就可以了，这道题大家要多理解一下。

第二题对应力扣编号为46的题目全排列

      接下来我们来到今天的第二道题目叫做全排列，这个其实大家应该都很熟悉，高中的排列组合大家应该都了解过，我们首先还是一起来看一下题目：

        题目要求很简单，大概就是打乱数组各个元素的位置，输出所有可能的情况，这里大家仍需要注意我们每一个元素还是都可以使用一次，因此这里还涉及到去重，我们当然还是通过回溯算法来解决，不过这里大家需要注意我们全排列与我们原来的组合，子集是不一样的，我们循环的时候应该每一次都是从头开始搜索，大家可以看一下代码随想录给出的图：

       大家可以看出，我们每一次都是从头开始取，这样我们才能保证得到想要的全排列，可以看出叶子节点，就是收割结果的地方。我们什么时候可以知道我们搜索到了叶子节点呢？其实就是我们的path的长度等于我们nums的长度的时候就是了，这样我们尝试写一下代码：

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(const vector<int> &nums, vector<bool> &used){//递归的终止条件if (path.size() == nums.size()){result.push_back(path);return;}//这里注意我们要从0开始不是startIndex因为我们每一个元素其实都要在我们的排列中出现for (int i = 0; i < nums.size(); ++i){if (used[i] == true) continue;//讲当前元素标记为使用过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;//恢复未使用过因为我们比如说1这个元素在[1,2,3]中使用过了但是我们在[1,3,2]里面还要再使用}}
public:vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

      这是我们的解题代码，其实大家注意到我们每一次都要从头开始搜索就可以，因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

第三题对应力扣编号为47的题目全排列 II

       这是我们今天必做题的最后一道，也是回溯算法章节的最后一道，后面的N皇后问题我要给大家讲一下，我们先来看这一道题目与上一道题目有什么不一样的地方：

       这里是包含可重复数字的序列，因此我们就要注意去重，保证每一个元素在排列中只会出现一次，我们其实需要对上一题的代码加以改造：

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(const vector<int> &nums, vector<bool> used){//递归的终止条件这个与上一道题目是一样的if (path.size() == nums.size()){result.push_back(path);return;}for (int i = 0; i < nums.size(); ++i){//这个不就是我们前面的去重问题的思路这个其实背都背过了if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;if (used[i] == false){used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, used);return result;}
};

   这里我就不多解释了，其实去重思路前面讲过了，剩下的与上一道题目没有太大的区别，我们看着今天的选做题N皇后。

第四题N皇后原题对应力扣题号51

      我看了力扣的原题，我想给大家一道其他的N皇后的问题，这道题来自蓝桥云课题库题目编号1508的题目：

        大家来看一下我原来备考蓝桥杯刷过的一道题目，这道题目要求我们求有多少种符合条件的放置方法，首先我们看到题目我们可以了解同一行，同一列，以及成45度角的地方都不允许出现两个皇后，否则会相互攻击，这样这道题目我们其实还是用我们以前的回溯算法来解决，我给出AC这道题目的代码：

#include <iostream>using namespace std;const int N = 15;
//注意我们这里使用的是整性数组不能用bool类型的数组
//原因是一个位置不一定只被一个皇后攻击只有这个位置没有任何皇后攻击的时候才可以放 
int vis[N][N];
//这个是我们地图的边长与我们要输出的答案的总数 
int n, ans;void dfs(int dep)
{//递归的终止条件搜索到最后一层表示找到了一个解 if (dep == n + 1){ans ++;return;}//遍历这一层的每一个位置 for (int i = 1; i <= n; ++i){if (vis[dep][i]) continue;//这是排除所有的列 for (int _i = 1; _i <= n; ++_i) vis[_i][i]++;//排除右上角成45度角的位置 for (int _i = dep,  _j = i; _i >= 1 &&  _j <= n; --_i,++_j) vis[_i][_j]++;//排除右下角45度角的位置for (int _i = dep, _j = i; _i <= n &&  _j <= n; ++_i, ++_j) vis[_i][_j]++;//排除左上角45度角的位置for (int _i = dep, _j = i; _i >= 1 &&  _j >= 1; --_i,--_j) vis[_i][_j]++;//排除左下角45角的位置for (int _i = dep, _j = i; _i <= n &&  _j >= 1; ++_i,--_j) vis[_i][_j]++;dfs(dep + 1);//这个很重要我们继续搜索下一层//接下来是恢复现场也就是回溯 for (int _i = 1; _i <= n; ++_i) vis[_i][i]--;for (int _i = dep,  _j = i; _i >= 1 &&  _j <= n; --_i,++_j) vis[_i][_j]--;for (int _i = dep, _j = i; _i <= n &&  _j <= n; ++_i, ++_j) vis[_i][_j]--;for (int _i = dep, _j = i; _i >= 1 &&  _j >= 1; --_i,--_j) vis[_i][_j]--;for (int _i = dep, _j = i; _i <= n && _j >= 1; ++_i,--_j) vis[_i][_j]--;}
}int main()
{//这个大家可能不了解这个是取消同步流使得输入输出更快 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;//我们从第一层开始搜索 dfs(1);cout << ans << '\n';return 0;
}

       dfs其实还是我们的递归，我们是按层来搜索的，说俗了就是行，首先我们还是给出递归的终止条件就是可以搜索到最后一层这样就说明我们找到了一种符合条件的解，最后我们输出ans就可以，这就是今天的题目。

今日总结

        回溯算法其实并不是一个时间复杂度很低的算法，我们其实一般不怎么使用，但是有些题目我们必须得使用，组合问题，子集，全排列，分割回文串，有效的IP地址等题目很好地锻炼了我们回溯算法的思想，注意递归三部曲，还要注意一些需要考虑去重地题目，到这里我们的回溯算法就告一段落了，接下来我们将走进贪心算法。我们明天见！