Share my 44ms C++ easy to understand


  • 0
    L
    class Solution {
    public:
    	vector<vector<int>> permuteUnique(vector<int>& nums)
    	{
    		vector<vector<int>> ret;
    		if (nums.size() == 0)return ret;
    		unordered_set<int> exist;
    		vector<int> stack;
    		std::sort(nums.begin(), nums.end());
    		permuteUnique(nums, 0, ret, stack, exist);
    		return ret;
    	}
    private:
    	void permuteUnique(vector<int>& nums, int cur, vector<vector<int>> &ret, vector<int> &stack, unordered_set<int> &exist)
    	{
    		for (int j = cur; j<nums.size(); j++)
    		{
    			 
    			if (exist.count(j))continue;
    			if (j >= nums.size())break;
    			exist.insert(j);
    			stack.push_back(nums[j]);
    			if (stack.size() == nums.size())
    			{
    				ret.push_back(stack);
    				stack.pop_back();
    				exist.erase(j);
    				continue;
    			}
    			for (int i = 0; i<nums.size(); i++)
    			{
    				if (exist.count(i))continue;
    				else
    					permuteUnique(nums, i, ret, stack, exist);
    				break;
    			}
    			stack.pop_back();
    			exist.erase(j);
    			j++;
    			while ( j<nums.size()&&nums[j] == nums[j -1])
    			j++;
    			j--;
    		}
    	}
    };

Log in to reply
 

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