A simple C++ solution in only 20 lines


  • 107
    G
    class Solution {
    public:
        void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
            if (i == j-1) {
                res.push_back(num);
                return;
            }
            for (int k = i; k < j; k++) {
                if (i != k && num[i] == num[k]) continue;
                swap(num[i], num[k]);
                recursion(num, i+1, j, res);
            }
        }
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());
            vector<vector<int> >res;
            recursion(num, 0, num.size(), res);
            return res;
        }
    };

  • 2
    W

    You can swap the two elements back after the recursive call, and use reference for num to reduce to O(1) space.

    also the use of variable j is not necessary


  • 8
    Y

    Not true. Swap back make this method invalid. It has to be O(n) space. About j is true though


  • 0
    Y

    Very nice solution! simple code and works!


  • 0
    V

    very nice idea , but I think using hash_map is cheaper


  • 2
    A

    Why does swapping back make this method invalid? I tried, and it did fail, but I do not know why. Thanks.


  • 2
    Y

    First, note that any modification to the loop change the behavior of the loop. If you swap it back, the algorithm completely changes. It is not a straight forward algorithm. Try write down "12345" and simulate on paper to see how it changes. You will notice the difference between "swap them back" and "not swap them back".
    That also answers why we cannot use reference(because we cannot swap everything back in each recursion level.)


  • 1
    A

    Thanks for your response. Yes, I understand that any modification to the loop change the behavior of the loop. I think both of the following ways work: 1, use reference and swapping back, 2, no reference and no swapping back. I have checked and verified that both work for "12345" and also for "112345". Unfortunately, the method of "using reference and swapping back" caused "Output Limit Exceeded" in OJ. It is a mystery to me why it fails, though the logic is very clear and clean. The following is the code, just a little change from guoang's:

    class Solution {

    public:

    void recursion(vector<int>& num, int i, vector<vector<int> > &res) {
    
        if (i == num.size()-1) {
    
            res.push_back(num);
    
            return;
    
        }
    
        for (int k = i; k < num.size(); k++) {
    
            if (i != k && num[i] == num[k]) continue;
    
            swap(num[i], num[k]);
    
            recursion(num, i+1, res);
    
            swap(num[i], num[k]);
    
        }
    
    }
    
    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(), num.end());
    
        vector<vector<int> >res;
    
        recursion(num, 0, res);
    
        return res;
    
    }
    

    };


  • 1
    Y

    You are outputing a lot of duplicate solutions if there is something like "1112345". guoang's solution is following strictly the "next permutation" order. If you swap it back, you are not following that order, which result in a lot of duplicate solutions. Google "next permutation" if you don't know what it is.


  • 0
    A

    The condition "if (i != k && num[i] == num[k]) continue;" in the for loop has ruled out all the possibilities of duplicate. If anybody wants to help me with my question, you may safely assume that I know what "next permutation" is. I appreciate your kindness and patience.


  • 2
    Y

    No it does not. It appears to rule out duplicates on one recursive level, but the final results will have duplicate. Try run it on your own computer with input 111222333 and you will see.


  • 1
    A

    Thank you very much, yetaila! I run the code for "1122", checked all steps very carefully and found out the duplicates.


  • 0
    Y

    You are welcome!


  • 2
    C

    Nice code! I take quite a long time to understand this. In each loop, the num[i+1:] can keep its order as well. That's real interesting!

    And a improvement to reduce the space complexity on the parameter num

    class Solution {
    public:
        vector<vector<int> > resList;
        vector<vector<int>> permute(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            dfs(0, nums);
            return resList;
        }
    
        void dfs(int i, vector<int>& nums){
            if (i >= nums.size()){
                resList.push_back(nums);
                return;
            }
            int p;
            for (p = i; p < nums.size(); p++){
                if (p > i && nums[p] == nums[i]) continue;
                swap(nums[i], nums[p]);
                dfs(i + 1, nums);
            }
            int last = nums[i];
            for (p = i + 1;p < nums.size(); p++)
                nums[p - 1] = nums[p];
            nums[p - 1] = last;
        }
    };

  • 3
    J

    Here is the working Java version I wrote:

      public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        permutating(ans, nums, 0);
        return ans;
    }
    
    private void permutating(List<List<Integer>> ans, int[] nums, int start) {
    	if (start == nums.length) {
    		List<Integer> li = new ArrayList<>();
    		for (int n : nums) {
    			li.add(n);
    		}
    		ans.add(li);
    		return;
    	}
    	for (int i = start; i < nums.length; i++) {
    		if (i != start && nums[start] == nums[i]) {
    			continue;
    		}
    		swap(nums, start, i);
    		permutating(ans, Arrays.copyOf(nums, nums.length), start+1);
    	}
    }
    
    private void swap(int[] nums, int i, int j) {
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }

  • 0
    S

    Hi..,

    i was trying the same problem in C#.Getting duplicate in result.What is purpose of using "Arrays.copyOf(nums, nums.length)"..


  • 0
    J

    The key to make the following duplicate control statement work is to use "pass by values" of nums array to the next level of recursion:

    if (i != start && nums[start] == nums[i]) {
    continue;
    }

    As people discussed earlier in the thread, "pass by value" has totally different recursion sequence from "pass by reference". "pass by reference " won't work in this algorithm. Java doesn't have pass by value syntax for array(neither C#), so I pass a copy to preserve the original array.


  • 0
    L

    Nice solution. Rewriting it in C# below:

    public IList<IList<int>> PermuteUnique(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums);
        dfs(result, nums, 0);
        return result;
    }
    private void dfs(IList<IList<int>> result, int[] nums, int iCur){
        if(iCur == nums.Length - 1) result.Add(new List<int>(nums));
        else
            for(int i = iCur; i < nums.Length; i++){
                if(i != iCur && nums[iCur] == nums[i]) continue;
                int[] newNums = new int[nums.Length];
                nums[iCur] = nums[iCur] ^ nums[i] ^ (nums[i] = nums[iCur]);
                Array.Copy(nums, newNums, nums.Length);
                dfs(result, newNums, iCur + 1);
            }
    }

  • 0
    S

    Hi, I tried to trace the procedure of how "num" changes and how the code reach the answer. But I didn't find obvious rule to how change "num". Can you tell how did you come up with this idea and why you implement it like this? Thank you!


  • 16
    T

    Basically your idea is sorting first and then applying same method for permutation I. Here is my code which is similar except I use reference for num in the helper function, why did I get TLE on [3,3,0,0,2,3,2]. Could anyone give me a hint???

    class Solution {
    public:
    void helper(vector<vector<int>>& res, int pos, vector<int>& nums)//0...pos-1 already permutated
    {
        if(pos == nums.size())
        {
            res.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); ++i)
        {
            if(i != pos && nums[i] == nums[pos]) continue;
            swap(nums[i], nums[pos]);
            helper(res, pos + 1, nums);
            swap(nums[i], nums[pos]);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.empty())return res;
        sort(nums.begin(), nums.end());
        helper(res, 0, nums);
        return res;
    }
    

    };


Log in to reply
 

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