Problem

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Analysis

This problem is similar to http://mytechroad.com/leetcode-c-permutations/
The only difference is that the number may be repeated, thus we need to deal with the special case when
– nums[i-1] is used, and nums[i]==num[i-1]

Time complexity: O(n!), the same analysis with previous problem

Solution

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> allPer;
        if(nums.size()==0) return allPer;
        vector<int> currPer;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        findAllPer(nums, allPer, currPer, used);
        return allPer;
        
    }
    
    void findAllPer(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
        if(currPer.size() == nums.size()){
            allPer.push_back(currPer);
            return;
        }
        
        for(int i=0; i<nums.size(); i++){
            //Case 1: if current number is used, skip
            if(used[i]) continue;
            //Case 2: if current number is not used, but previous number is equal to current number, skip
            if(i>0 && nums[i]==nums[i-1] && used[i-1]) continue;
            
            //Otherwise: DFS to find all permutation 
            used[i] = true;
            currPer.push_back(nums[i]);
            findAllPer(nums, allPer, currPer, used);
            currPer.pop_back();
            used[i] = false;
        }
    }
};