up 排列

rongweihe · web-flow · commit 27ac2f35b2bd · 2022-01-22T12:17:55.000+08:00
up 排列
diff --git a/algorithms/algo_notes/回溯专题.md b/algorithms/algo_notes/回溯专题.md
@@ -321,6 +321,11 @@ public:
 ## 子集II  https://leetcode-cn.com/problems/subsets-ii/
 思路：回溯+ 去重
 
+- 同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2
+- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
+- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
+- 而我们要对同一树层使用过的元素进行跳过
+
 ```c++
 class Solution {
 private:
@@ -350,3 +355,76 @@ public:
     }
 };
 ```
+
+## 排列 1 + 2
+排列1：https://leetcode-cn.com/problems/permutations/
+
+排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
+used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
+
+```c++
+class Solution {
+public:
+    std::vector<vector<int>> ret;
+    std::vector<int> path;
+    std::vector<vector<int>> permute(vector<int>& nums) {
+        ret.clear();
+        path.clear();
+        std::vector<bool> used(nums.size(), false);
+        backtrack(nums, used);
+        return ret;
+    }
+    void backtrack(std::vector<int>& nums, std::vector<bool>& used) {
+        if (path.size() == nums.size()) {
+            ret.push_back(path);
+            return;
+        }
+        for (int i = 0; i < nums.size(); ++i) {
+            if (used[i] == true) continue;//记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
+            path.push_back(nums[i]);
+            used[i] = true;
+            backtrack(nums, used);
+            used[i] = false;
+            path.pop_back();
+        }
+    }
+};
+
+```
+
+排列2：给定一个可包含重复数字的序列，要返回所有不重复的全排列。
+https://leetcode-cn.com/problems/permutations-ii/
+
+```c++
+class Solution {
+public:
+    std::vector<vector<int>> ret;
+    std::vector<int> path;
+    std::vector<vector<int>> permuteUnique(vector<int>& nums) {
+        ret.clear();
+        path.clear();
+        std::sort(nums.begin(), nums.end());//排序
+        std::vector<bool> used(nums.size(), false);
+        backtrack(nums, used);
+        return ret;
+    }
+    void backtrack(std::vector<int>& nums, std::vector<bool>& used) {
+        if (path.size() == nums.size()) {
+            ret.push_back(path);
+            return;
+        }
+        for (int i = 0; i < nums.size(); ++i) {
+            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
+            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
+            // 如果同一树层nums[i - 1]使用过则直接跳过
+            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
+            if (used[i] == true) continue;//u记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
+            path.push_back(nums[i]);
+            used[i] = true;
+            backtrack(nums, used);
+            used[i] = false;
+            path.pop_back();
+        }
+    }
+};
+```
