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:
    vectorint>> res;
    vectorint>> 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;isize();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:
    vectorint>> res; 
    vectorint>> 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;isize();i++)
        {
            if(i>start&&nums[i]==nums[i-1])//剪枝逻辑，值相同的树枝，只遍历第一条
            {
                continue;
            }
            track.push_back(nums[i]);
            backtrack(nums,i+1,track);
            track.pop_back();
        }
    }
};