up 组合总和II

rongweihe · web-flow · commit f66a1917251c · 2022-01-18T23:19:59.000+08:00
组合总和II
diff --git a/algorithms/algo_notes/回溯专题.md b/algorithms/algo_notes/回溯专题.md
@@ -194,3 +194,54 @@ public:
     }
 };
 ```
+
+## 组合总和II https://leetcode-cn.com/problems/combination-sum-ii/
+给你一个由候选元素组成的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
+
+candidates 中的每个元素在每个组合中只能使用 一次 。
+
+注意：解集不能包含重复的组合。 
+
+来源：力扣（LeetCode）
+链接：https://leetcode-cn.com/problems/combination-sum-ii
+著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
+
+思路： 
+
+组合II 递归三部曲
+- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
+- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
+- 要对同一树层使用过的元素进行跳过
+
+参考卡神思路：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E5%9B%9E%E6%BA%AF%E4%B8%89%E9%83%A8%E6%9B%B2
+
+class Solution {
+public:
+    std::vector<std::vector<int>> ret;
+    std::vector<int> path;
+    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
+        std::vector<bool> used(candidates.size(),false);
+        ret.clear();
+        path.clear();
+        std::sort(candidates.begin(), candidates.end());
+        backtrack(candidates, 0, 0, target, used);
+        return ret;
+    }
+    void backtrack(vector<int>& candidates,int sum, int start_index, int target, std::vector<bool>& used) {
+        if (sum == target) {
+            ret.push_back(path);
+            return;
+        }
+        
+        for (int i = start_index; i < candidates.size() && sum + candidates[i] <= target ; ++i) {
+            if ( i > 0 && candidates[i] == candidates[i - 1] && used[candidates[i - 1]] == false) continue;
+            sum += candidates[i];
+            used[candidates[i]] = true;
+            path.push_back(candidates[i]);
+            backtrack(candidates, sum, i + 1, target, used);//每个数只能用一次
+            path.pop_back();
+            used[candidates[i]] = false;
+            sum -= candidates[i];
+        }
+    }
+};
