47.全排列II | 90.子集II
47.全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路：
回溯算法秒杀所有排列/组合/子集问题 :: labuladong的算法小抄 (gitee.io)
先排序，让重复的元素挨到一起
相邻相等的前一个元素没有被遍历过，那么这个要跳过
例子：[2,2`,2``]，要保持这三个相等元素的相对顺序不变，即没用2，就不能用2`
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());//排序，让重复的元素挨到一起
vector<int> track;
vector<bool> used(nums.size(),false);
backtrack(nums,track,used);
return res;
}
void backtrack(vector<int>& nums,vector<int>& track,vector<bool>& used)
{
if(track.size()==nums.size())//触发结束条件（到达决策树底）
{
res.push_back(track);
return ;
}
for(int i=0;i<nums.size();i++)
{
if(used[i])//排除不合法的选择（用过的不能再用了）
{
continue;
}
//相邻相等的前一个元素没有被遍历过，那么这个要跳过
//例子：[2,2`,2``]，要保持这三个相等元素的相对顺序不变，即没用2，就不能用2`
if(i>0 && nums[i]==nums[i-1] && !used[i-1])
{
continue;
}
track.push_back(nums[i]);
used[i]=true;
backtrack(nums,track,used);
track.pop_back();
used[i]=false;
}
}
};90.子集II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
先排序，让重复的元素挨到一起
if(i>start&&nums[i]==nums[i-1]) //剪枝逻辑，值相同的树枝，只遍历第一条
决策树中标注了start的变化：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> track;
sort(nums.begin(),nums.end());//排序，让相同的元素挨到一起
backtrack(nums,0,track);
return res;
}
void backtrack(vector<int>& nums,int start,vector<int>& track)
{
res.push_back(track);
for(int i=start;i<nums.size();i++)
{
if(i>start&&nums[i]==nums[i-1])//剪枝逻辑，值相同的树枝，只遍历第一条
{
continue;
}
track.push_back(nums[i]);
backtrack(nums,i+1,track);
track.pop_back();
}
}
};