# 0047. 全排列 II ## 題目地址(47. 全排列 II) <https://leetcode-cn.com/problems/permutations-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個可包含重復數字的序列，返回所有不重復的全排列。 示例: 輸入: [1,1,2] 輸出: [ [1,1,2], [1,2,1], [2,1,1] ] ``` ``` ## 前置知識 - 回溯法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目是求集合，并不是`求極值`，因此動態規劃不是特別切合，因此我們需要考慮別的方法。 這種題目其實有一個通用的解法，就是回溯法。 網上也有大神給出了這種回溯法解題的 [通用寫法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)>)，這里的所有的解法使用通用方法解答。 除了這道題目還有很多其他題目可以用這種通用解法，具體的題目見后方相關題目部分。 我們先來看下通用解法的解題思路，我畫了一張圖：  > 圖是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，僅做參考。 通用寫法的具體代碼見下方代碼區。 ## 關鍵點解析 - 回溯法 - backtrack 解題公式 ## 代碼 - 語言支持: Javascript，Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=47 lang=javascript * * [47] Permutations II * * https://leetcode.com/problems/permutations-ii/description/ * * algorithms * Medium (39.29%) * Total Accepted: 234.1K * Total Submissions: 586.2K * Testcase Example: '[1,1,2]' * * 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] * ] * * */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">backtrack</span>(<span class="hljs-params">list, nums, tempList, visited</span>) </span>{ <span class="hljs-keyword">if</span> (tempList.length === nums.length) <span class="hljs-keyword">return</span> list.push([...tempList]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-title">// 和46.permutations的區別是這道題的nums是可以重復的</span> <span class="hljs-title">// 我們需要過濾這種情況</span> <span class="hljs-keyword">if</span> (visited[i]) <span class="hljs-keyword">continue</span>; <span class="hljs-title">// 不能用tempList.includes(nums[i])了，因為有重復</span> <span class="hljs-title">// visited[i - 1] 這個判斷容易忽略</span> <span class="hljs-keyword">if</span> (i > <span class="hljs-params">0</span> && nums[i] === nums[i - <span class="hljs-params">1</span>] && visited[i - <span class="hljs-params">1</span>]) <span class="hljs-keyword">continue</span>; visited[i] = <span class="hljs-params">true</span>; tempList.push(nums[i]); backtrack(list, nums, tempList, visited); visited[i] = <span class="hljs-params">false</span>; tempList.pop(); } } <span class="hljs-title">/** * @param {number[]} nums * @return {number[][]} */</span> <span class="hljs-keyword">var</span> permuteUnique = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> list = []; backtrack( list, nums.sort((a, b) => a - b), [], [] ); <span class="hljs-keyword">return</span> list; }; ``` ``` Python3 code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">permuteUnique</span><span class="hljs-params">(self, nums: List[int])</span> -> List[List[int]]:</span> <span class="hljs-string">"""與46題一樣，當然也可以直接調用itertools的函數，然后去重"""</span> <span class="hljs-keyword">return</span> list(set(itertools.permutations(nums))) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">permuteUnique</span><span class="hljs-params">(self, nums: List[int])</span> -> List[List[int]]:</span> <span class="hljs-string">"""自己寫回溯法，與46題相比，需要去重"""</span> <span class="hljs-title"># 排序是為了去重</span> nums.sort() res = [] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_backtrace</span><span class="hljs-params">(nums, pre_list)</span>:</span> <span class="hljs-keyword">if</span> len(nums) <= <span class="hljs-params">0</span>: res.append(pre_list) <span class="hljs-keyword">else</span>: <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(nums)): <span class="hljs-title"># 如果是同樣的數字，則之前一定已經生成了對應可能</span> <span class="hljs-keyword">if</span> i > <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> nums[i] == nums[i<span class="hljs-params">-1</span>]: <span class="hljs-keyword">continue</span> p_list = pre_list.copy() p_list.append(nums[i]) left_nums = nums.copy() left_nums.pop(i) _backtrace(left_nums, p_list) _backtrace(nums, []) <span class="hljs-keyword">return</span> res ``` ``` ## 相關題目 - [31.next-permutation](31.next-permutation.html) - [39.combination-sum](39.combination-sum.html) - [40.combination-sum-ii](40.combination-sum-ii.html) - [46.permutations](46.permutations.html) - [60.permutation-sequence](60.permutation-sequence.html)(TODO) - [78.subsets](78.subsets.html) - [90.subsets-ii](90.subsets-ii.html) - [113.path-sum-ii](113.path-sum-ii.html) - [131.palindrome-partitioning](131.palindrome-partitioning.html)