leetcode 47. Permutations II[排列]

https://leetcode.com/problems/permutations-ii/

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

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

全排列去重

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int> v, int len, vector<int> nums) {
        //printf("size=%d\n", v.size());
        if (v.size() == len) {
            vector<int> t;
            //printf("len = %d\n", len);
            for (int i = 0; i < v.size(); i ++) {
                t.push_back(nums[v[i]]);
                //printf("i=%d, nums[i]=%d\n", i, nums[i]);
            }
            ans.push_back(t);
            return;
        }
        for (int i = 0; i < len; i ++) {
            vector<int>::iterator iter;
            iter = find(v.begin(), v.end(), i);
            if(iter == v.end()) {
                //printf("i=%d\n", i);
                v.push_back(i);
                dfs(v, len, nums);
                v.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++) {
            vector<int>v(1, i);
            dfs(v, nums.size(), nums);
        }
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
};

去看看更优雅的做法

利用STL的

next_permutation

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        ans.push_back(nums);
        while (next_permutation(nums.begin(), nums.end())) {
            if (nums != ans.back())
                ans.push_back(nums);
        }
        return ans;
    }
};

快了很多QAQ