47. Permutations II
C++，这道题和剑指offer中字符串全排列是一样的。
思路如下：
- 其实这个全排列算法就是固定一个数的位置(left)，然后从下一位数再开始全排列(递归过程)…直到最后一位数，模拟手动全排列的过程；
- 所以如果要去重的话，只要控制每次排列时，固定的那个数是不一样的就行了；
- 因为固定的数不一样，那从这个数开始产生的全排列就不一样。所以只要让每次的left位置的数不一样就行，所以先sort，保证只有相邻的数是可能一样的；
- 然后
if (i != left && nums[left] == nums[i]) continue;使得每次固定的数(即left)都不一样，就行了。
代码如下：
class Solution {
vector<vector<int>> ans;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
perm(nums, 0, nums.size() - 1);
return ans;
}
void perm(vector<int> nums, int left, int right) {
if (left == right)
ans.push_back(nums);
else {
for (int i = left; i <= right; i++) {
if (i != left && nums[left] == nums[i]) continue; # 去重
swap(nums[left], nums[i]);
perm(nums, left + 1, right);
}
}
}
};
