Simple 20-line C++ solution using backtracking with explanation


  • 3
    J
    // This question is mostly the same as Permutation I, but with an unordered_set to avoid duplicates. 
    // The key point to avoid duplicates is to avoid selecting repeated numbers at the same position.
    class Solution {
    public:
        void myPermuteUnique(vector<vector<int>>& results, vector<int>& nums, int index){
            if (index == nums.size()) {
                results.push_back(nums);
                return;
            }
            unordered_set<int> M;
            for (int i = index; i < nums.size(); i ++) {
                if (M.find(nums[i]) != M.end()) continue; 
                else M.insert(nums[i]);
                swap(nums[i], nums[index]);
                myPermuteUnique(results, nums, index+1);
                swap(nums[i], nums[index]);
            }
        }
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> results;
            myPermuteUnique(results, nums, 0);
            return results;
        }
    };

Log in to reply
 

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