代码随想录算法训练营第二十九天|491.递增子序列、46.全排列

491.递增子序列

回溯三部曲

递归函数参数

本题求子序列，很明显一个元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置

递增子序列大小至少为2

单层搜索逻辑

使用set来对本层元素进行去重

unordered_set<int>uset;// 使用set来对本层元素进行去重for(inti=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();}

巧妙的是可以用数组标记是否使用过。

46.全排列

排列问题和组合有区别

回溯三部曲

递归函数参数

需要一个used数组，标记已经选择的元素

递归终止条件

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点

单层搜索的逻辑

排列问题，每次都要从头开始搜索 一个排列里一个元素只能使用一次

for(inti=0;i<nums.size();i++){if(used[i]==true)continue;// path里已经收录的元素，直接跳过used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}

47.全排列 II

同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重

voidbacktracking(vector<int>&nums,vector<bool>&used){// 此时说明找到了一组if(path.size()==nums.size()){result.push_back(path);return;}for(inti=0;i<nums.size();i++){// used[i - 1] == true，说明同一树枝nums[i - 1]使用过// used[i - 1] == false，说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if(i>0&&nums[i]==nums[i-1]&&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;}}}