LeetCode-47-全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Code

//Time O(n!+logN)
//Space O(n+n)
class Solution {
private:
    vector<vector<int>> res;
public:
    //每个数可以出现的位置
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        vector<int> cs(nums.size());
        DFS(0,0,nums,cs,used);
        return res;
    }
    //index为cs数组中的位置
    void DFS(int index,int start,vector<int>& nums,vector<int>& cs,vector<bool>& used){
        if(index==cs.size()){
            res.push_back(cs);
            return;
        }
        //枚举当前数可以放在哪些位置
        for(int i=start;i<nums.size();i++){
            if(!used[i]){
                used[i]=true;
                cs[i] = nums[index];
                //若后一个数与前一个数相同，则后一个数只能放到该数的后面
                if(index+1<nums.size()&&nums[index+1]==nums[index])
                    DFS(index+1,i+1,nums,cs,used);
                else
                    DFS(index+1,0,nums,cs,used);
                used[i]=false;
            }
        }
    }
};