计算机科学基础leetcode刷题回溯算法
Source
Edit
History

40. 组合总和 II

Problem: 40. 组合总和 II

Reference

https://www.programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E6%80%9D%E8%B7%AF

思路

其他与回溯算法一致，没有任何区别。每一层选取自己后面的元素，但是这里要注意相同层不能选取同一个元素。

最终重要一点就是，事先将元素排序，那么每一层就可以直接在自己后面找到自己相同的元素了sort(candidates.begin(),candidates.end());。

不过这个去重有点抽象,代码随想录中这样解释:

1
2
// used[i - 1] == true，说明同一树**枝**candidates[i - 1]使用过
// used[i - 1] == false，说明同一树**层**candidates[i - 1]使用过

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    int sum;
    vector<bool> used;
    void backTracing(vector<int>& candidates, int target, int index) {
        if (sum > target)
            return;
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backTracing(candidates, target, i + 1);
            path.pop_back();
            sum -= candidates[i];
            used[i] = false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        used = vector<bool>(candidates.size(),false);
        sort(candidates.begin(),candidates.end());
        backTracing(candidates, target, 0);
        return res;
    }
};