acash's blog

By acash, history, 5 weeks ago, ,

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;
}
};


• -5

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by acash (previous revision, new revision, compare).
 » 5 weeks ago, # |   +8 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.
•  » » 5 weeks ago, # ^ |   0 I just checked on leetcode it is printing correct you can also see in console https://leetcode.com/problems/permutations-ii/
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Oh, I missed the sort in the main. Try $1, 2, 2$.