Permutations II

Question

Problem Statement

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers [1,2,2] the unique permutations are:

  1. [
  3.     [1,2,2],
  5.     [2,1,2],
  7.     [2,2,1]
  9. ]

Challenge

Do it without recursion.

题解1 - backtracking

在上题的基础上进行剪枝，剪枝的过程和 Unique Subsets 一题极为相似。为了便于分析，我们可以先分析简单的例子，以 [1, 2_1, 2_2] 为例。按照上题 Permutations 的解法，我们可以得到如下全排列。

  1. $$[1, 2_1, 2_2]$$
  2. $$[1, 2_2, 2_1]$$
  3. $$[2_1, 1, 2_2]$$
  4. $$[2_1, 2_2, 1]$$
  5. $$[2_2, 1, 2_1]$$
  6. $$[2_2, 2_1, 1]$$

从以上结果我们注意到1和2重复，5和3重复，6和4重复，从重复的解我们可以发现其共同特征均是第二个 2_2 在前，而第一个 2_1 在后，因此我们的剪枝方法为：对于有相同的元素来说，我们只取不重复的一次。嗯，这样说还是有点模糊，下面以 [1, 2_1, 2_2] 和 [1, 2_2, 2_1] 进行说明。

首先可以确定 [1, 2_1, 2_2] 是我们要的一个解，此时list为 [1, 2_1, 2_2], 经过两次list.pop_back()之后，list为 [1], 如果不进行剪枝，那么接下来要加入list的将为 2_2, 那么我们剪枝要做的就是避免将 2_2 加入到list中，如何才能做到这一点呢？我们仍然从上述例子出发进行分析，在第一次加入 2_2 时，相对应的visited[1]为true(对应 2_1)，而在第二次加入 2_2 时，相对应的visited[1]为false，因为在list为 [1, 2_1] 时，执行list.pop_back()后即置为false。

一句话总结即为：在遇到当前元素和前一个元素相等时，如果前一个元素visited[i - 1] == false, 那么我们就跳过当前元素并进入下一次循环，这就是剪枝的关键所在。另一点需要特别注意的是这种剪枝的方法能使用的前提是提供的nums是有序数组，否则无效。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: A list of integers.
  5.      * @return: A list of unique permutations.
  6.      */
  7.     vector<vector<int> > permuteUnique(vector<int> &nums) {
  8.         vector<vector<int> > ret;
  9.         if (nums.empty()) {
  10.             return ret;
  11.         }
  13.         // important! sort before call `backTrack`
  14.         sort(nums.begin(), nums.end());
  15.         vector<bool> visited(nums.size(), false);
  16.         vector<int> list;
  17.         backTrack(ret, list, visited, nums);
  19.         return ret;
  20.     }
  22. private:
  23.     void backTrack(vector<vector<int> > &result, vector<int> &list, \
  24.                    vector<bool> &visited, vector<int> &nums) {
  25.         if (list.size() == nums.size()) {
  26.             result.push_back(list);
  27.             // avoid unnecessary call for `for loop`, but not essential
  28.             return;
  29.         }
  31.         for (int i = 0; i != nums.size(); ++i) {
  32.             if (visited[i] || (i != 0 && nums[i] == nums[i - 1] \
  33.                 && !visited[i - 1])) {
  34.                 continue;
  35.             }
  36.             visited[i] = true;
  37.             list.push_back(nums[i]);
  38.             backTrack(result, list, visited, nums);
  39.             list.pop_back();
  40.             visited[i] = false;
  41.         }
  42.     }
  43. };

源码分析

Unique Subsets 和 Unique Permutations 的源码模板非常经典！建议仔细研读并体会其中奥义。

后记：在理解 Unique Subsets 和 Unique Permutations 的模板我花了差不多一整天时间才基本理解透彻，建议在想不清楚某些问题时先分析简单的问题，在纸上一步一步分析直至理解完全。

题解2 - 字典序

Permutation 的题使用字典序的做法其实更为简单，且为迭代的解法，效率也更高。代码和之前的 Permutations 那道题一模一样。

Java

  1. class Solution {
  2.     /**
  3.      * @param nums: A list of integers.
  4.      * @return: A list of unique permutations.
  5.      */
  6.     public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
  7.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  8.         if (nums == null || nums.size() == 0) return result;
  10.         // deep copy(do not change nums)
  11.         List<Integer> perm = new ArrayList<Integer>(nums);
  12.         // sort first!!!
  13.         Collections.sort(perm);
  15.         while (true) {
  16.             // step0: add perm into result
  17.             result.add(new ArrayList<Integer>(perm));
  19.             // step1: search the first num[k] < num[k+1] backward
  20.             int k = -1;
  21.             for (int i = perm.size() - 2; i >= 0; i--) {
  22.                 if (perm.get(i) < perm.get(i + 1)) {
  23.                     k = i;
  24.                     break;
  25.                 }
  26.             }
  27.             // if current rank is the largest, exit while loop
  28.             if (k == -1) break;
  30.             // step2: search the first perm[k] < perm[l] backward
  31.             int l = perm.size() - 1;
  32.             while (l > k && perm.get(l) <= perm.get(k)) l--;
  34.             // step3: swap perm[k] with perm[l]
  35.             Collections.swap(perm, k, l);
  37.             // step4: reverse between k+1 and perm.length-1;
  38.             reverse(perm, k + 1, perm.size() - 1);
  39.         }
  41.         return result;
  42.     }
  44.     private void reverse(List<Integer> nums, int lb, int ub) {
  45.         for (int i = lb, j = ub; i < j; i++, j--) {
  46.             Collections.swap(nums, i, j);
  47.         }
  48.     }
  49. }

源码分析

见前一题，略。

复杂度分析

略

Reference