# Why this backtracking algorithm doesn't work

• ``````vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
permuteUniqueHelper(nums, 0, ret);
return ret;
}

void permuteUniqueHelper(vector<int>& nums, int b, vector<vector<int>>& ret) {
if (b == nums.size()) {
ret.push_back(nums);
return;
}
for (int i = b; i < nums.size(); i += 1) {
if (i != b && (nums[i] == nums[b] || nums[i] == nums[i - 1])) continue;
swap(nums[i], nums[b]);
permuteUniqueHelper(nums, b + 1, ret);
swap(nums[i], nums[b]);
}
}``````

• I want to know it too

• some example, there are more than way to get 1551
1[1]55 -> 1551
1[1]55 -> 15[1]5 -> 1551

• I'm confused too. It seems that the order of these permutations in the answer must also be matched.

• Coz u swap nums[i] n nums[b] after recall permuteUniqueHelper.
Then ur nums[i] will not change, but ur "if continue " can only make sure that the number with same value of nums[i] will not be considered again, which is means that, for 1,1,1,2,2,2,3,3,3, the value "1" will not repeat because nums[i] is 1, but all "2" n "3" will repeat because nums[i] is still "1", ur "if continue" doesn't work.

• Swaping causes the sort order to be disturbed hence failing the algorithms

• Assume at the beginning the subarray(b, end) is sorted, but once you swap nums[b] with another number in the middle of subarray(b, end), you break the order of the subarray, hence the "nums[i] == nums[i - 1]" check doesn't work as you expect, it's possible that nums[i + 1] == nums[i - 1] but nums[i] != nums[i - 1]

• It's a math problem actually, solution is as follows which is my favourite.

``````vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int size = nums.size(), i, j;
vector<vector<int>> vv;
while(true)
{
vv.push_back(nums);
i = size-2, j = size-1;
while(i>0 && nums[i]>=nums[i+1]) i--;
while(j>0 && nums[i]>=nums[j]) j--;
if(j == 0) break;
swap(nums[i++], nums[j]);
j = size-1;
while(i<j)  swap(nums[i++], nums[j--]);
}
return vv;
}
``````

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