[Leetcode C++] Permutations II


Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:



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


class Solution {
    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()){
        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;
            findAllPer(nums, allPer, currPer, used);
            used[i] = false;

Leave a Reply

Your email address will not be published. Required fields are marked *