491. 递增子序列
思路：
这道题和子集2不同的地方在于本题不能进行排序，排序之后会出现新的子集，不和题意。本题可以用一个set类型的变量来记录先前已经遍历过的数组，如果先前已经遍历了，后续就不用再遍历。
代码：
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> usedset;
for(int i=index;i<nums.size();i++)
{
if ((!path.empty() && nums[i] < path.back())|| usedset.find(nums[i]) != usedset.end())
{
continue;
}
usedset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return res;
}
};
46. 全排列
思路：
这道题是排列问题，123与213是属于两个排列，这与以往的组合问题不一样。本题使用布尔类型的数组used来标记哪一位已经使用过，在每层遍历的过程中都从第一个元素开始遍历，但是如果使用了就跳过。
代码：
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;
path.push_back(nums[i]);
used[i]=true;
backtracking(nums,used);
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used);
return res;
}
};
47. 全排列 II
思路：
这道题的思路和第46题一致，只不过题目给定的数组中含有重复的元素，所以在进行排列之前先进行去重操作，去重的算法与第40题一致。
代码：
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 && used[i-1]==false && nums[i]==nums[i-1])continue;
if(used[i]==true)continue;
path.push_back(nums[i]);
used[i]=true;
backtracking(nums,used);
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used);
return res;
}
};
