C++: Permutations II

Thought Process

To generate all unique permutations of a given array (which may contain duplicates), we use backtracking. First, we sort the array to group duplicates together. During the backtracking process, we skip duplicate elements to avoid redundant permutations. This ensures that we generate all unique permutations efficiently. 

class Solution {
public:
    void backTrack(vector<vector<int>> &ans, vector<int> &tmp, vector<int> nums, vector<bool> &used){

        if(tmp.size()==nums.size()){
            ans.push_back(tmp);
            return;
        }

        for(int i=0;i<nums.size();i++){

            // Condition to avoid duplicates
            // If element is already is used then continue OR
            // If current Element == Previous Element and Previous Element is not included that means the 
            // permutation
            // which is going to build now will be same as permutations build by previous element. Hence,
            // it will create duplicates.
            if(used[i]==true || (i>0 && nums[i]==nums[i-1] && used[i-1]==false))
                continue;

            used[i] = true;
            tmp.push_back(nums[i]);
            backTrack(ans,tmp,nums,used);
            tmp.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> tmp;

        sort(nums.begin(),nums.end());
        vector<bool> used(n,false);

        backTrack(ans,tmp,nums,used);
        return ans;
    }
};

Code Complexity

Time Complexity: O(n * n!)

The algorithm generates all unique permutations of the input array, resulting in n! permutations in the worst case, and each permutation takes O(n) time to construct, where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary vector stores intermediate results.

Code copied!