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;}
};