Merge branch 'master' of https://github.com/azl397985856/leetcode

lucifer · lucifer · commit 70166f44a85a · 2021-01-04T10:22:41.000+08:00
diff --git a/problems/46.permutations.md b/problems/46.permutations.md
@@ -50,6 +50,12 @@ https://leetcode-cn.com/problems/permutations/
 
 通用写法的具体代码见下方代码区。
 
+以 [1,2,3] 为例，我们的逻辑是：
+
+- 先从 [1,2,3] 选取一个数。
+- 然后继续从 [1,2,3] 选取一个数，并且这个数不能是已经选取过的数。
+- 重复这个过程直到选取的数字达到了 3。
+
 ## 关键点解析
 
 - 回溯法
@@ -84,32 +90,6 @@ var permute = function (nums) {
 
 Python3 Code:
 
-```Python
-class Solution:
-    def permute(self, nums: List[int]) -> List[List[int]]:
-        """itertools库内置了这个函数"""
-        return itertools.permutations(nums)
-
-    def permute2(self, nums: List[int]) -> List[List[int]]:
-        """自己写回溯法"""
-        res = []
-        def _backtrace(nums, pre_list):
-            if len(nums) <= 0:
-                res.append(pre_list)
-            else:
-                for i in nums:
-                    # 注意copy一份新的调用，否则无法正常循环
-                    p_list = pre_list.copy()
-                    p_list.append(i)
-                    left_nums = nums.copy()
-                    left_nums.remove(i)
-                    _backtrace(left_nums, p_list)
-        _backtrace(nums, [])
-        return res
-```
-
-Python Code:
-
 ```Python
 class Solution:
     def permute(self, nums: List[int]) -> List[List[int]]:
@@ -120,7 +100,7 @@ class Solution:
     def permute2(self, nums: List[int]) -> List[List[int]]:
         """自己写回溯法"""
         res = []
-        def _backtrace(nums, pre_list):
+        def backtrack(nums, pre_list):
             if len(nums) <= 0:
                 res.append(pre_list)
             else:
@@ -130,23 +110,23 @@ class Solution:
                     p_list.append(i)
                     left_nums = nums.copy()
                     left_nums.remove(i)
-                    _backtrace(left_nums, p_list)
-        _backtrace(nums, [])
+                    backtrack(left_nums, p_list)
+        backtrack(nums, [])
         return res
 
     def permute3(self, nums: List[int]) -> List[List[int]]:
         """回溯的另一种写法"""
         res = []
         length = len(nums)
-        def _backtrack(start=0):
+        def backtrack(start=0):
             if start == length:
                 # nums[:] 返回 nums 的一个副本，指向新的引用，这样后续的操作不会影响已经已知解
                 res.append(nums[:])
             for i in range(start, length):
                 nums[start], nums[i] = nums[i], nums[start]
-                _backtrack(start+1)
+                backtrack(start+1)
                 nums[start], nums[i] = nums[i], nums[start]
-        _backtrack()
+        backtrack()
         return res
 ```
 
diff --git a/problems/47.permutations-ii.md b/problems/47.permutations-ii.md
@@ -34,18 +34,26 @@ 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 and nums[i] == nums[i - 1] and visited[i - 1]**， 则不进行选取即可。
+
+经过这样的处理，每次实际上都是从后往前依次重复的数。仍然以上面的 [1,1,2]  为例。[1,1,2] 这个排列一定是先取的第二个 1，再取第一个 1，最后取的 2。因为如果先取的第一个 1，那么永远无法取到三个数，便形成了一个不可行解。
 
 ## 关键点解析
 
@@ -61,39 +69,14 @@ https://leetcode-cn.com/problems/permutations-ii/
  * @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]
- * ]
- *
- *
  */
 function backtrack(list, nums, tempList, visited) {
   if (tempList.length === nums.length) return list.push([...tempList]);
   for (let i = 0; i < nums.length; i++) {
     // 和46.permutations的区别是这道题的nums是可以重复的
     // 我们需要过滤这种情况
-    if (visited[i]) continue; // 不能用tempList.includes(nums[i])了，因为有重复
-    // visited[i - 1] 这个判断容易忽略
-    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue;
+    if (visited[i]) continue; // 同一个数字不能用两次
+    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue; // 同样值的数字不能用两次
 
     visited[i] = true;
     tempList.push(nums[i]);
@@ -128,23 +111,23 @@ class Solution:
 
     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
         """自己写回溯法，与46题相比，需要去重"""
-        # 排序是为了去重
+        # 排序是为了方便去重
         nums.sort()
         res = []
-        def _backtrace(nums, pre_list):
+        def backtrack(nums, pre_list):
             if len(nums) <= 0:
                 res.append(pre_list)
             else:
                 for i in range(len(nums)):
-                    # 如果是同样的数字，则之前一定已经生成了对应可能
+                    # 同样值的数字只能使用一次
                     if i > 0 and nums[i] == nums[i-1]:
                         continue
                     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, [])
+                    backtrack(left_nums, p_list)
+        backtrack(nums, [])
         return res
 ```
 
@@ -154,7 +137,7 @@ class Solution:
 - [39.combination-sum](./39.combination-sum.md)
 - [40.combination-sum-ii](./40.combination-sum-ii.md)
 - [46.permutations](./46.permutations.md)
-- [60.permutation-sequence](./60.permutation-sequence.md)(TODO)
+- [60.permutation-sequence](./60.permutation-sequence.md)
 - [78.subsets](./78.subsets.md)
 - [90.subsets-ii](./90.subsets-ii.md)
 - [113.path-sum-ii](./113.path-sum-ii.md)
diff --git a/problems/78.subsets.md b/problems/78.subsets.md
@@ -28,7 +28,7 @@ https://leetcode-cn.com/problems/subsets/
 
 ## 前置知识
 
-- 回溯
+- [回溯](https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md)
 
 ## 公司
 
@@ -39,18 +39,9 @@ https://leetcode-cn.com/problems/subsets/
 
 ## 思路
 
-这道题目是求集合，并不是`求极值`，因此动态规划不是特别切合，因此我们需要考虑别的方法。
+回溯的基本思路清参考上方的回溯专题。
 
-这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](<https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)>)，这里的所有的解法使用通用方法解答。
-除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
-
-我们先来看下通用解法的解题思路，我画了一张图：
-
-![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu2o05lsj31190u0jw4.jpg)
-
-> 每一层灰色的部分，表示当前有哪些节点是可以选择的， 红色部分则是选择路径。1，2，3，4，5，6 则分别表示我们的 6 个子集。
-
-通用写法的具体代码见下方代码区。
+子集类题目和全排列题目不一样的点在于其需要在递归树的所有节点执行**加入结果集**，这一操作，而不像全排列需要在叶子节点执行**加入结果集**。
 
 ## 关键点解析
 
