# 13 lines C++ backtracking

• My solution for Permutations I.

Solution for Permutations II is similar to Permutations I, the only difference is that we CAN'T swap back after each permutation, cause we want to pick a new different number for position `i` in each loop.

For example, suppose array nums = [1, 1, 2, 2, 3], first we swap nums[0] = 1 with the first different number nums[2] = 2, after first swap, nums = [2, 1, 1, 2, 3], then if we swap back `1` with `2`, nums = [1, 1, 2, 2, 3].

Now, we want to pick nums[4] = 3 as a new number for position `0`, but nums[3] = 2 would be considered the new different number because we swap the number '1' back to position `0`, so we will swap nums[0] with nums[3], nums = [2, 1, 2, 1, 3], so the same number '2' appears twice at position `0`, which cause the repeated outcomes.

``````class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>>res;
DFS(res, nums, 0);
return res;
}

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

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