Unique Permutations · 數據結構與算法/leetcode/lintcode題解

# Permutations II ### Source - leetcode: [Permutations II | LeetCode OJ](https://leetcode.com/problems/permutations-ii/) - lintcode: [(16) Permutations II](http://www.lintcode.com/en/problem/permutations-ii/) ### Problem 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,2,2], [2,1,2], [2,2,1] ] ~~~ #### Challenge Do it without recursion. ### 題解1 - backtracking 在上題的基礎上進行剪枝，剪枝的過程和 [Unique Subsets](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/unique_subsets.html) 一題極為相似。為了便于分析，我們可以先分析簡單的例子，以 [1,21,22][1, 2_1, 2_2][1,21,22] 為例。按照上題 Permutations 的解法，我們可以得到如下全排列。 1. [1,21,22][1, 2_1, 2_2][1,21,22] 1. [1,22,21][1, 2_2, 2_1][1,22,21] 1. [21,1,22][2_1, 1, 2_2][21,1,22] 1. [21,22,1][2_1, 2_2, 1][21,22,1] 1. [22,1,21][2_2, 1, 2_1][22,1,21] 1. [22,21,1][2_2, 2_1, 1][22,21,1] 從以上結果我們注意到`1`和`2`重復，`5`和`3`重復，`6`和`4`重復，從重復的解我們可以發現其共同特征均是第二個 222_222 在前，而第一個 212_121 在后，因此我們的**剪枝方法為：對于有相同的元素來說，我們只取不重復的一次。**嗯，這樣說還是有點模糊，下面以 [1,21,22][1, 2_1, 2_2][1,21,22] 和 [1,22,21][1, 2_2, 2_1][1,22,21] 進行說明。首先可以確定 [1,21,22][1, 2_1, 2_2][1,21,22] 是我們要的一個解，此時`list`為 [1,21,22][1, 2_1, 2_2][1,21,22], 經過兩次`list.pop_back()`之后，`list`為 [1][1][1], 如果不進行剪枝，那么接下來要加入`list`的將為 222_222, 那么我們剪枝要做的就是避免將 222_222 加入到`list`中，如何才能做到這一點呢？我們仍然從上述例子出發進行分析，在第一次加入 222_222 時，相對應的`visited[1]`為`true`(對應 212_121)，而在第二次加入 222_222 時，相對應的`visited[1]`為`false`，因為在`list`為 [1,21][1, 2_1][1,21] 時，執行`list.pop_back()`后即置為`false`。一句話總結即為：在遇到當前元素和前一個元素相等時，如果前一個元素`visited[i - 1] == false`, 那么我們就跳過當前元素并進入下一次循環，這就是剪枝的關鍵所在。另一點需要特別注意的是這種剪枝的方法能使用的前提是提供的`nums`是有序數組，否則無效。 ### C++ ~~~ class Solution { public: /** * @param nums: A list of integers. * @return: A list of unique permutations. */ vector<vector<int> > permuteUnique(vector<int> &nums) { vector<vector<int> > ret; if (nums.empty()) { return ret; } // important! sort before call `backTrack` sort(nums.begin(), nums.end()); vector<bool> visited(nums.size(), false); vector<int> list; backTrack(ret, list, visited, nums); return ret; } private: void backTrack(vector<vector<int> > &result, vector<int> &list, \ vector<bool> &visited, vector<int> &nums) { if (list.size() == nums.size()) { result.push_back(list); // avoid unnecessary call for `for loop`, but not essential return; } for (int i = 0; i != nums.size(); ++i) { if (visited[i] || (i != 0 && nums[i] == nums[i - 1] \ && !visited[i - 1])) { continue; } visited[i] = true; list.push_back(nums[i]); backTrack(result, list, visited, nums); list.pop_back(); visited[i] = false; } } }; ~~~ ### 源碼分析 Unique Subsets 和 Unique Permutations 的源碼模板非常經典！建議仔細研讀并體會其中奧義。后記：在理解 Unique Subsets 和 Unique Permutations 的模板我花了差不多一整天時間才基本理解透徹，建議在想不清楚某些問題時先分析簡單的問題，在紙上一步一步分析直至理解完全。 ### 題解2 - 字典序 Permutation 的題使用字典序的做法其實更為簡單，且為迭代的解法，效率也更高。代碼和之前的 Permutations 那道題一模一樣。 ### Java ~~~ public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) { return result; } Arrays.sort(nums); while (true) { // step1: add list to result List<Integer> list = new ArrayList<Integer>(); for (int i : nums) { list.add(i); } result.add(list); // step2: find nums[k] < nums[k + 1] backward int k = -1; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { k = i; break; } } if (k == -1) break; // step3: swap with nums[l] int l = nums.length - 1; while (l > k && nums[l] <= nums[k]) { l--; } int temp = nums[l]; nums[l] = nums[k]; nums[k] = temp; // step4: reverse between k+1, nums.length - 1 reverse(nums, k + 1, nums.length - 1); } return result; } private void reverse(int[] nums, int lb, int ub) { while (lb < ub) { int temp = nums[lb]; nums[lb] = nums[ub]; nums[ub] = temp; lb++; ub--; } } } ~~~ ### 源碼分析見前一題，略。 ### 復雜度分析略 ### Reference - [Permutation II | 九章算法](http://www.jiuzhang.com/solutions/permutations-ii/)