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;}}}
网友评论