Update 47.permutations-ii.md

azl397985856 · web-flow · commit 3c640f79352c · 2021-01-01T15:39:01.000+08:00
diff --git a/problems/47.permutations-ii.md b/problems/47.permutations-ii.md
@@ -34,18 +34,24 @@ https://leetcode-cn.com/problems/permutations-ii/
 
 这道题目是求集合，并不是`求极值`，因此动态规划不是特别切合，因此我们需要考虑别的方法。
 
-这种题目其实有一个通用的解法，就是回溯法。
-网上也有大神给出了这种回溯法解题的
-[通用写法](<https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)>)，这里的所有的解法使用通用方法解答。
+这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的
+[通用写法](<https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)>)，这里的所有的解法都使用通用方法解答。
+
 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
 
-我们先来看下通用解法的解题思路，我画了一张图：
+这道题和第 46 题不一样的点在于其有重复元素。比如题目给的 [1,1,2]。
+
+如果按照 46 题的解法，那么就会有重复的排列。 回顾一下 46 题我们的逻辑。以 [1,1,2] 为例，我们的逻辑是：
+
+- 先从 [1,1,2] 选取一个数。
+- 然后继续从 [1,1,2] 选取一个数，并且这个数不能是已经选取过的数。
+- 重复这个过程直到选取的数字达到了 3。
 
-![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu6qwpr4j31190u0jw4.jpg)
+如果继续沿用上面的逻辑，那么我们是永远无法拿到三个数字的，因此我们的逻辑需要变化。 这里我的算法是记录每一个被选取的索引，而不是值，这就保证了**同一个数字不会被选取多次，并且可以选取所有数字了**。
 
-> 图是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，仅做参考。
+不过这还是有一个问题。 仍然以 [1,1,2]  为例，如果第一次选取了第一个1，第二次选取了第二个1，这就产生了一个组合 [1,1,2]。 如果继续第一次选取了第二个 1，而第二次选取了第一个 1，那么又会产生组合 [1,1,2]，可以看出这两个组合是重复的。
 
-通用写法的具体代码见下方代码区。
+一个解决方案是对 nums 进行一次排序，并规定如果 **i > 0 && nums[i] === nums[i - 1] && visited[i - 1]**， 则不进行选取即可。
 
 ## 关键点解析
 
