题目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

分析

这题与上一题的不同之处为可能含有相同的元素。那么对于结果的每一位，只要跳过之前出现过的数字即可。需要注意的是，这一位的跳过不能影响下一位的使用。对于第46题稍作修改即可。

实现

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        vector<int> path;
        vector<vector<int>> ans;
        solve(nums, used, path, ans);
        return ans;
    }
private:
    void solve(vector<int> &nums, vector<bool> &used,
                              vector<int> &path, vector<vector<int>> &ans){
        if(path.size()==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]) continue;
            if(i!=0 && nums[i]==nums[i-1] && !used[i-1]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            solve(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

思考

偷懒的做法也可以直接使用std::permutation()==
但是这对于提高毫无作用，面试的时候考官也肯定会让你重新实现的。
另外看题解的时候发现了c++中也有for_each()感觉很神奇，赶紧恶补了下。
然而有些还是看不懂...c++果然可怕==