Short 40ms C++ solution similar to Permutation I solution


  • 10
    D

    This is like the Permutation I solution, but we use an unordered_set to avoid swapping elements that are the same (which would generate identical permutations).

    class Solution {
    public:
    
        void permuteUniqueHelper(int i, vector<int>& nums, vector<vector<int> >& result) {
            if (i == nums.size()) { result.emplace_back(nums); return; }
            unordered_set<int> st;
            for (int j = i; j < nums.size(); ++j) {
                if (st.count(nums[j]) == 1) { continue; }
                st.insert(nums[j]);
                std::swap(nums[i], nums[j]);
                permuteUniqueHelper(i + 1, nums, result);
                std::swap(nums[i], nums[j]);
            }
        }
        
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int> > result;
            permuteUniqueHelper(0, nums, result);
            return result;
        }
    };

  • 0
    L

    This should be the best post built on the permutation-I problem


Log in to reply
 

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