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;
}
};
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.
I just checked on leetcode it is printing correct you can also see in console https://leetcode.com/problems/permutations-ii/
Oh, I missed the sort in the main. Try $$$1, 2, 2$$$.