491. 非递减子序列
此前通过used数组去重的操作的前提是需要首先给数组排序，本题不可以，因为求递增子序列时，原先的序列并不是一定递增的，此时进行排序后，此时递增子序列会包含其他原先不是原先数据的子序列。
递归参数：index一定是需要的，记录下一层递归分割的起始位置。
递归终止条件：由N叉树可以看出，当子集内个数大于1的时候便可以收获结果
单层搜索的逻辑：在同一树层中，不需要重复读取相同的树，需要对其剪裁，由于不能使用used数组，可以使用哈希判断当前树层是否存在相同的数，unordered_set<int> uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！还需要判断树枝上的树是否会小于path最后一个数，如果小于了就不是递增子序列了
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int> &nums,int index){
if(path.size()>1)res.push_back(path);
unordered_set<int> hash;
for(int i=index;i<nums.size();i++){
if(!path.empty()&&nums[i]<path.back()||hash.find(nums[i])!=hash.end())continue;
hash.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
path.clear();
res.clear();
backtracking(nums,0);
return res;
}
};46. 全排列
递归函数参数:首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
单层搜索的逻辑:排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>&nums,vector<bool> used){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(used[i]==true)continue;
used[i]=true;
path.push_back(nums[i]);
backtracking(nums,used);
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
path.clear();
res.clear();
vector<bool> used(nums.size(), false);
backtracking(nums,used);
return res;
}
};47. 全排列 II
本题需要进行树层去重操作，树枝去重操作逻辑：当前元素与上一层相等并且use数组的前一个为0（use[i-1]=false），表明是需要进行树层去重， 使用used数组可以将树枝去重和树层区分开来。
同时因为本题需要的是排列问题，i从0开始，为了判断一个元素是否去过，仍然可以使用used数组进行判断。
递归函数参数:used数组与传入nums
递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
单层搜索的逻辑:排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,vector<bool> used){
if(path.size()==nums.size()){
res.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);
used[i]=false;
path.pop_back();}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
path.clear();
res.clear();
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used);
return res;
}
};
