Recursion WITH pass by reference (beat 90%)


  • 1
    W

    As many posts already discussed, we cannot use the same recursion with pass by reference as "Permutation I" which does not have duplicates.
    The reason is this recursion algorithm relies on the numbers are sorted. When we pass by reference and swap the numbers, the sorted order is violated. However, without passing by reference, the time and space we spend copying the number vector is bad.
    I made one improvement over the pass by reference method by checking not only the duplicates between the two swapped numbers, but also whether there is any duplicate number in front of the ready-to-swap number.

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(), nums.end());
        	vector<vector<int>> result;
        	permutation(nums, 0, result);
        	return result;
        }
        
    private:
    	void permutation( vector<int>& nums, int ind, vector<vector<int>>& result) {
    		if (ind >= nums.size() - 1) {
    			result.push_back(nums);
    			return;
    		}
    		for (int i = ind; i < nums.size(); i++) {
                        bool duplicate = false;
    	            for(int j = ind; j < i; j++) {
    	                if(nums[j] == nums[i]) {
    	                    duplicate = true;
    	                    break;
    	                }
    	            }
    	            if(!duplicate) {
        		       swap( nums[ind],nums[i]);
        	               permutation(nums, ind+1, result);
        		       swap(nums[i], nums[ind]);
    	             }
                    }
    	}
    };
    
    

Log in to reply
 

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