Don't confuse, just the same idea as Combination with duplicates


  • 0
    L

    I believe you were confused as I did. Why the solution used in combination failed here.

    No, it doesn't. Just sort the rest of the array after swap. Remember, your solution is based on a sorted array!

    vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            vector<int> path;
            premuteUnique(nums, 0, res,path);
            return res;
        }
        
        void premuteUnique(vector<int>& nums, int r, vector<vector<int>>& res, vector<int>& path)
        {
            if (r == nums.size()) {
                res.push_back(path);
                return;
            }
            
            for (int i=r; i <nums.size(); i++)
            {
                while (i!=r &&   i !=nums.size() && nums[i-1] == nums[i]) i++;
                
                if (i == nums.size()) return;
                
                path.push_back(nums[i]);
                
                swap(nums[i], nums[r]);
                
                // ---- Must sort it, otherwise, the sub-problem is not the same
                auto temp(nums);
                sort(temp.begin()+r+1, temp.end());
                // ----
                
                premuteUnique(temp, r+1, res, path);
                
                swap(nums[i], nums[r]);
                
                path.pop_back();
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.