acash's blog

By acash, history, 5 weeks ago, In English,

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] I am failing on a large test cases can anyone help me where i am doing wrong? please:)

class Solution {
public:
    void solve(vector<vector<int>>&res,int j,vector<int>&nums){
        if(j==nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i=j;i<nums.size();i++){
            if(i==j||nums[i]!=nums[j]){
            swap(nums[i],nums[j]);
            solve(res,j+1,nums);
            swap(nums[i],nums[j]);}
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>>res;
        sort(nums.begin(),nums.end());
        solve(res,0,nums);
        return res;
    }
};
 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

At least one small case where this code seems to fail is on input $$$2, 1, 1$$$, you generate the permutation $$$1, 1, 2$$$ two times: in the first way, you make the swaps $$$2, 1, 1$$$ -> $$$1, 2, 1$$$ -> $$$1, 1, 2$$$, and in the second, the swaps $$$2, 1, 1$$$ -> $$$1, 1, 2$$$.

I didn't actually test that this happens, this is just off reading the code.