代码随想录第二十九天打卡| 491.递增子序列，46.全排列，47.全排列 II

491.递增子序列

本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。

代码随想录

视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

class Solution {
public:vector<vector<int>>res;vector<int>path;void Traversal(vector<int>nums,int startindex){if (path.size()>1)res.push_back(path);unordered_set<int>uset;//只在本层有效for (int i=startindex;i<nums.size();i++){if (uset.find(nums[i])!=uset.end())continue;if (!path.empty() && nums[i]<path.back())continue;uset.insert(nums[i]);path.push_back(nums[i]);Traversal(nums, i+1);path.pop_back();//进入下一层的时候会自动消除，又在本层不能消除}}vector<vector<int>> findSubsequences(vector<int>& nums) {Traversal(nums,0);return res;}
};

总结

感觉明白了。

46.全排列

本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex

代码随想录

视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

class Solution {
public:vector<vector<int>>res;vector<int>path;void Traversal(vector<int>nums,int startindex,vector<bool>used){if (path.size()==nums.size()){res.push_back(path);return;}for (int i=0;i<nums.size();i++){if (used[i])continue;used[i]=true;path.push_back(nums[i]);Traversal(nums,i+1,used);used[i]=false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<bool>used(nums.size(),false);Traversal(nums,0,used);return res;}
};

47.全排列 II

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行

代码随想录

视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

class Solution {
public:vector<vector<int>>res;vector<int>path;void Traversal(vector<int>nums,int startindex,vector<bool>used,vector<bool>visited){if (path.size()==nums.size()){res.push_back(path);return;}for (int i=0;i<nums.size();i++){if (used[i])continue;//这个其实涉及到纵向,所以要用回溯,跳过的值可能不在同一层。if (i>0 && nums[i]==nums[i-1] && visited[i-1]==false)continue;used[i]=true;visited[i]=true;path.push_back(nums[i]);Traversal(nums,i+1,used,visited);used[i]=false;visited[i]=false;path.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool>used(nums.size(),false);sort(nums.begin(),nums.end());vector<bool>visited(nums.size(),false);Traversal(nums,0,used,visited);return res;}
};