Description

Submission

After sorting the nums, we only need to make sure that the same value is not used in the same place and the same recursion twice.

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<bool> taken(nums.size(), false);
        vector<int> hand;
        backtrack(res, nums, taken, hand, nums.size());
        return res;
    }
private:
    void backtrack(vector<vector<int>>& res, vector<int>& nums,
                   vector<bool>& taken, vector<int>& hand, int k) {
        if(k == 0) {
            res.push_back(hand);
            return;
        }
        int prev_pick = 999999;
        for(int i = 0; i < nums.size(); ++i) {
            if(!taken[i] && prev_pick != nums[i]) {
                prev_pick = nums[i];
            } else {
                continue;
            }
            hand.push_back(prev_pick);
            taken[i] = true;
            backtrack(res, nums, taken, hand, k - 1);
            hand.pop_back();
            taken[i] = false;
        }
    }
};