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

  • 0

    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()) {
            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;
                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]);

Log in to reply

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