[LeetCode 47] Permutations II

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]
]

Diffculty
Medium

Similar Problems
[LeetCode ] Next Permutation Medium [LeetCode ] Permutations II Medium [LeetCode ] Palindrome Permutation II Medium

Analysis

思路 这道题跟 LeetCode 46 题思路相同，只是多了重复元素，所以需要在解集中去重复。 思路和 combination II, subset II 的去重复基本一致。也即，对于有重复元素的情况，先排序，然后每层递归跳过重复数字。 这里，需要用一个临时数组去标记每个元素是否已经访问过。

注意这里的重复数字指的是一直到当前递归层，还未被使用的数字中的重复。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &A) {
        if(A.empty()) return {{}};
        sort(A.begin(), A.end()); // 先排序，很重要！

        vector<vector<int>> result;
        vector<int> sol;
        vector<bool> used(A.size(), false);

        permuteUnique(A, used, sol, result);
        return result;
    }

    void permuteUnique(vector<int> &A, vector<bool> &used, vector<int> &sol, vector<vector<int>> &result) {
        if(sol.size() == A.size()) {
            result.push_back(sol);
            return;
        }

        for(int i = 0; i < A.size(); i++) {
            if(used[i]) continue; // 如果用过
            if(i > 0 && A[i] == A[i-1] && !used[i-1]) continue; // 如果当前元素没用过，但是跟前面元素一样，而且前面一个也没用过，那么直接返回
            used[i] = true;
            sol.push_back(A[i]);
            permuteUnique(A, used, sol, result);
            sol.pop_back();
            used[i] = false;
        }
    }
};

算法3： 我们知道 C++ STL 中有个函数 next_permutation，这个函数时求某个排列的下一个大的排列。 所谓的下一个大的排列可以如下解释：如果把数组元素看成是某个字符，这些字符组成一个字符串，下一个大的排列就是比当前排列代表的字符串更大（按字典序比较），且不存在介于两个字符串之间的字符串。 例如对于字符串 abc，它的下一个大排列是 acb。

对于某个排列，我们如下求它的下一个大的排列： 从最尾端开始往前寻找两个相邻的元素，两者满足i < ii（令第一个元素为i，第二个元素为ii） 如果没有找到这样的一对元素则，表明当前的排列是最大的，没有下一个大的排列 如果找到，再从末尾开始找出第一个大于i的元素，记为j 交换元素i, j，再将ii后面的所有元素颠倒排列(包括ii) 按照的STL实现，如果某个排列没有比他大的下一个排列，调用这个函数还是会把原排列翻转，即得到最小的排列 有了这个函数后，这一题，我们先对数组按照升序排序，这样初始排列就是最小的，然后循环对数组求next_permutation，直到找不到下一个大的排列。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        if(num.size() == 0)return res;
        sort(num.begin(), num.end());
        res.push_back(num);
        while(mynext_permutation(num))res.push_back(num);
        return res;
    }

    bool mynext_permutation(vector<int>&num) {
        int n = num.size();
       if(n <= 1)return false;
       for(int i = n-2, ii = n-1; i >= 0; i--,ii--) {
           if(num[i] < num[ii]) {
               int j = n-1;
               while(num[j] <= num[i])j--;//从尾部找到第一个比num[i]大的数，一定可以找到
               swap(num[i], num[j]);
               reverse(num.begin()+ii, num.end());
               return true;
           }
       }
       reverse(num.begin(), num.end());
       return false;
    }
};

// 另外： STL 还有一个 prev_permutation 函数，求某个排列的上一个比他小的排列，方法和 next_permutation 相似：

对于某个排列，我们如下求它的上一个更小的排列：

从最尾端开始往前寻找两个相邻的元素，两者满足i > ii（令第一个元素为i，第二个元素为ii） 如果没有找到这样的一对元素则，表明当前的排列是最小的，没有下一个更小的排列 如果找到，再从末尾开始找出第一个小于i的元素，记为j 交换元素i, j，再将ii后面的所有元素颠倒排列（包括ii） 按照的STL实现，如果某个排列没有比他小的下一个排列，调用这个函数还是会把原排列翻转，即得到最大的排列 有了这个函数后，这一题，我们先对数组按照降序排序，这样初始排列就是最大的，然后循环对数组求prev_permutation，直到找不到下一个更小的排列。