回溯算法 491. 递增子序列 题意：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有
回溯算法
491. 递增子序列
题意：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例：
思路：本题其实和数组的组合很像，只是我们不会无脑的存储组合数组了，而是有两个条件：
- 数组大小必须大于1
- 数组必须为递增数组
为了满足以上两个条件，我们分别对存储和组合操作进行限制
存储时，组合数组tmp必须大于1；组合操作时，当待加入元素小于组合数最后一个元素时，或待加入元素已经被使用时，出现重复组合时，跳过。
此外，我们还创建了一个数组，用于标记已经被使用的元素，同层无法使用已经被标记的元素
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void IncreaseSequence(vector<int>& nums,int begin)
{
if(tmp.size()>=2)//这里不需要返回，因为我们还有更大的组合需要保存；如果返回，那就只能返回大小为2的组合了
{
arr.push_back(tmp);
}
vector<int> s;
for(int i=begin;i<nums.size();i++)
{
if(!tmp.empty()&&nums[i]<tmp.back()||find(s.begin(),s.end(),nums[i])!=s.end())//排除两种方法不成组合：1.下一个元素小于最后一个元素 2.该元素已经被使用
{
continue;
}
tmp.push_back(nums[i]);
s.push_back(nums[i]);//这里是同层的元素被使用的标记，不用回溯
IncreaseSequence(nums,i+1);
tmp.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
IncreaseSequence(nums,0);
return arr;
}46. 全排列
题意：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例：
思路：由于本题给出的数组中的元素是不重复的，因此，我们只需要考虑每个元素只拿一次就可以。
所以我们需要定一个block数组标记数组每层可以使用的元素，只要为0，那就是还没有被使用；为1就是被使用，直接跳过。最终在回溯终止条件中，只要有组合元素大小等于nums的大小即可存储
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void AllPermut(vector<int>& nums,vector<bool> block)
{
if(tmp.size()==nums.size())//组合数组的大小必须等于nums的大小
{
arr.push_back(tmp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(block[i]==true)//该元素被使用过直接跳过
{
continue;
}
tmp.push_back(nums[i]);
block[i]=true;//用于记录每一层被使用过的元素
AllPermut(nums,block);
block[i]=false;
tmp.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> block(nums.size(),false);
AllPermut(nums,block);
return arr;
}47. 全排列 II
题意：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例：
思路：本题的思路，其实和46.全排序几乎一样，就是在存储数组时不会那么无脑，需要判断组合数组是否已经被存储即可。还有一种思路是在形成组合数时进行操作，先将nums进行排序，然后在变量nums时，如果当前元素等于前一个元素，并且前一个元素未被使用，就说明该位置的元素已经在之前使用过了，去一层上的相同元素
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void AllPermut2(vector<int>& nums,vector<bool> block)
{
if(tmp.size()==nums.size())
{
if(find(arr.begin(),arr.end(),tmp)==arr.end())//再次判断，存储的组合必须是未保存的
{
arr.push_back(tmp);
}
return;
}
for(int i=0;i<nums.size();i++)
{
if(block[i]==true)
{
continue;
}
tmp.push_back(nums[i]);
block[i]=true;
AllPermut2(nums,block);
block[i]=false;
tmp.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> block(nums.size(),false);
AllPermut2(nums,block);
return arr;
} vector<vector<int>> arr;
vector<int> tmp;
void AllPermut2(vector<int>& nums,vector<bool> block)
{
if(tmp.size()==nums.size())
{
arr.push_back(tmp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(i>0&&nums[i-1]==nums[i]&&block[i-1]==false)
{
continue;
}
if(block[i]==false)
{
tmp.push_back(nums[i]);
block[i]=true;
AllPermut2(nums,block);
block[i]=false;
tmp.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> block(nums.size(),false);
sort(nums.begin(),nums.end());
AllPermut2(nums,block);
return arr;
}