我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

leetcode解题回溯篇_leetcode怎么删除提交记录

作者：我家小花儿 | 2024-02-19 23:51:39

踩

leetcode怎么删除提交记录

九、回溯算法

什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。

回溯法的效率

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

回溯模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1. 77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> result; // 存储全部符合条件的结果
        vector<int> temp; // 存储单个

        backtracking(n,k,1,result,temp);
        return result;

        // 组合问题，优先考虑回溯算法，回溯算法就要考虑回溯的模板
        // 首先，先确定下返回值和参数
        // 之后确定终止条件
        // 最后，本层的处理
    }
    // 1 2 3 4  k = 2;
    void backtracking(int n , int k , int depth,vector<vector<int>> &result,vector<int> & temp){
        if(temp.size() == k){
            result.push_back(temp);
            return;
        }
        for(int i = depth ; i <= n ; i++)
        {
            temp.push_back(i);
            backtracking(n,k,i + 1,result,temp);
            temp.pop_back();
        }
    }
};
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

按照树形结构来理解回溯问题，其实回溯问题也是一种暴力解法，但是相比于for循环嵌套，本题连嵌套都嵌套不了。而且这类组合的题目首先要想到的就是回溯算法，然后根据题目的具体要求，按照回溯的模板来确定如何解题：以本题为例，首先确定回溯函数的返回值和参数，返回值一般都为void，参数的话首先得有n，和k，然后由于是组合问题，避免重复的话得放上递归的深度depth。然后再确定终止条件，最后再是处理结果并且回溯。之后可以进行回溯的枝剪过程。

2. 216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:

    vector<vector<int>> result;
    vector<int> temp;

    vector<vector<int>> combinationSum3(int k, int n) {

        backtracking(k,n,1);
        return result;

    }

    void backtracking(int k, int n, int depth){
        if(temp.size() == k){
            int sum = 0;
            for(auto i : temp){
                sum+=i;
            }
            if(sum == n)
                result.push_back(temp);
            return;    
        }

        for(int i = depth ; i <= 9 ; i++){
            temp.push_back(i);
            backtracking(k,n,i + 1);
            temp.pop_back();
        }
    }
};
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

也是和上题一样的思路。

3. 17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<string> result;
    const vector<string> material = 
    {
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    vector<int> vec; // 4,6
    string temp;
    vector<string> letterCombinations(string digits) {

        if(digits == "")
            return result;
        int k = digits.size();
        for(auto c : digits){
            int cc = c - '0';
            vec.push_back(cc - 2);
        }

        backtracking(k,0);
        return result;
    }

    void backtracking(int k,int index){
        if(temp.size() == k){
            result.push_back(temp);
            return;
        }

        for(int i = 0 ; i < material[vec[index]].size(); i++){
            temp.push_back(material[vec[index]][i]);
            backtracking(k,index+1);
            temp.pop_back();
        }
    }

};
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
34
35
36
37
38
39
40
41
42
43
44

本题和前面两天略有不同，本题是求在不同集合中的元素组合。但还是把题目当成一个树的结构来做就不难写了。

4. 39. 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        backchacking(candidates,target,0,0);
        return result;
    }

    void backchacking(vector<int>& candidates, int target, int sum, int index){
        if(sum == target){
            result.push_back(temp);
            return;
        }else if(sum > target){
            return;
        }

        for(int i = index ; i < candidates.size() ; i++){
                temp.push_back(candidates[i]);
                sum+=candidates[i];
                backchacking(candidates,target,sum,i);
                sum-=candidates[i];
                temp.pop_back();
        }

    }
};
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

和前面题目最大的区别就是backchacking(candidates,target,sum,i);这里取的是I而不是I + 1 ，因为可以重复取元素，所有下一层递归还是接着从i这里开始取值。

5. 40. 组合总和2⃣️

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:

    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backchacking(candidates,target,0,0);
        return result;
    }

    void backchacking(vector<int>& candidates, int target, int sum, int index){

        if(sum == target){
            result.push_back(temp);
            return;
        }else if(sum > target){
            return;
        }
        int used = -1 ;
        for(int i = index ; i < candidates.size() && sum < target; i++){
                if(candidates[i] == used)
                    continue;
                used = candidates[i];
                temp.push_back(candidates[i]);
                used = candidates[i];
                sum+=candidates[i];
                backchacking(candidates,target,sum,i+1);
                sum-=candidates[i];
                temp.pop_back();
        }

    }
};
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
34

本题的主要难点在于去重上，正常用set转vector的话，会超时，所以得在代码逻辑中去重。而逻辑中去重的话，这边我的思路是先给candidates排个序，然后，如果for循环中当前元素和上一个元素相同的话，就直接continue，这样就避免了同一层中的重复。这样的思路好像是有点像之前做过的某道题，但我有点忘了是哪一道题了，也是得在代码逻辑中去重的。

6. 分割回文串

给你一个字符串 s，请你将 **s **分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

class Solution {
public:
    vector<vector<string>> result;
    vector<string> temp;
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return result;
    }

    void backtracking(string s, int index){

        if(index == s.size()){
            result.push_back(temp);
            return;
        }

        for(int i = index; i < s.size(); i++){
            string str = s.substr(index,i - index + 1);
            if(!judge(str)){
                continue;
            }
            temp.push_back(str);
            backtracking(s,i+1);
            temp.pop_back();
        }
    }

    bool judge(string str){

        string s = str;
        reverse(str.begin(),str.end());
        return s == str;
    }
};
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
34

本题是一个切割问题，同样是要按照一定的规则对字符串进行切割操作，主要说一下回溯的思路，首先回溯的终止条件是当切割到最后一个索引位置的时候就结束，这证明已经找到一个符合条件的切割了；然后就是如何切割，对于abcde这个字符串，第一刀可以是a｜bcde，ab｜cde，abc｜de 诸如此类，在对剩余的字符串进行第二刀、第三刀、第n刀。在for循环中，直接就对切出来的字串进行回文判断，判断是否是回文，如果不是，则直接continue；换刀的位置，如果是，则切下一刀。

7. 93.复原IP地址

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<string> result;
    string temp;
    vector<string> restoreIpAddresses(string s) {

        backtracking(s,0,0);
        return result;
    }

    void backtracking(string s, int index, int count){

        if(count == 4 && index == s.size()){
            result.push_back(temp);
            return;
        }

        for(int i = index; i < s.size(); i++){

            string str = s.substr(index, i - index + 1);
            if(str.size() > 3)
                continue;
            int num = stoi(str);
            if((str[0] == '0' && str.size() > 1) || num > 255 ){
                continue;
            }
            temp+=str;
            if(count != 3){
                temp+=".";
            }
            backtracking(s,i + 1, count + 1);
            if(count != 3){
                temp.erase(temp.size() - str.size() - 1,str.size() + 1);
            }else{
                temp.erase(temp.size() - str.size(), str.size());
            }
        }
    }

};
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
34
35
36
37
38
39
40

这题和上题其实差不多，甚至比上题还更简单一些感觉。思路也是一样。

值得注意的是，这边我遇到了越界的报错，最终发现是stoi的str超出了int的范围，所以最后加了个str的位数的判断，超出则直接continue

8. 78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> subsets(vector<int>& nums) {

        backtracking(nums,0,0);
        return result;
    }

    void backtracking(vector<int>& nums,int count,int index){
        if(count == nums.size()){
            result.push_back(temp);
            return;
        }

        for(int i = index; i < nums.size(); i++){
            // 不选当前元素
            backtracking(nums,count+1,i+1);
            // 选择当前元素
            temp.push_back(nums[i]);
            backtracking(nums,count+1,i+1);
            temp.pop_back();
        }

    }
};
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

本题主要是找自己，子集问题也习惯性使用回溯方法，在树的宽度上，遍历该集合，对于每一个元素，都有选or不选两种情况，弄清楚回溯的本质其实就是穷举，所以在for循环中进行了两次回溯，第一次是不选当前元素，第二次是选择当前元素。强行找的终止条件为进行了num.size()次选择。

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

这个就相当于不需要终止条件判断，即可存到结果中。

9. 90.子集II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backtracking(nums,0);
        return result;
    }
    void backtracking(vector<int>& nums,int index){

        result.push_back(temp);
        for(int i = index; i < nums.size(); i++){
            if(i > index && nums[i] == nums[i-1])
                continue;
            temp.push_back(nums[i]);
            backtracking(nums,i+1);
            temp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

本题主要在于会有重复，但是使用之前的在for循环中去重的思想易解决。

10. 491.递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }

    void backtracking(vector<int>& nums, int startIndex) {
        if (temp.size() > 1) {
            result.push_back(temp);
            // 注意这里不要加return，要取树上的节点
        }
        unordered_set<int> uset; // 使用set对本层元素进行去重
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!temp.empty() && nums[i] < temp.back())
                    || uset.find(nums[i]) != uset.end()) {
                    continue;
            }
            uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
            temp.push_back(nums[i]);
            backtracking(nums, i + 1);
            temp.pop_back();
        }
    }
};

// cannot AC
class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }

    void backtracking(vector<int>& nums, int index){

        if(temp.size() >= 2){
            result.push_back(temp);
        }

        for(int i = index; i < nums.size(); i++){
            unordered_set<int> tt;
            if(tt.find(nums[i]) != tt.end()){
                continue;
            }
            if(temp.empty()){
                temp.push_back(nums[i]);
                tt.insert(nums[i]);
                backtracking(nums,i + 1);
                temp.pop_back();
            }else{
                if(nums[i] >= temp.back()){
                    temp.push_back(nums[i]);
                    tt.insert(nums[i]);
                    backtracking(nums,i + 1);
                    temp.pop_back();
                }else{
                    continue;
                }
            }
        }
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

居然被这题卡住了很久，最终还是有答题的思路，但是不知道哪个环节出了些问题，就有一些小bug改不动，最后还是参考了下别人的，发现思路细节都一样，我的就是过不了，气。

说一下我的思考流程：最开始没仔细看，认为题目要求的必须是连续的子序列，一般来说子序列不都应该是连续的嘛，然后发现二重循环就能求解，提交后发现不对，仔细看给的示例，原来可以不连续。然后同样是同一层去重，在每一层使用一个set来记录是否使用过，使用过则直接continue；不符合条件的也直接continue；本题由于不能对原数组进行排序，所以不能用之前的套路写，只能用set来保存使用过的元素。

但是明明两种的逻辑一样，不知道为啥就是不能通过呢？算了，不死磕了，之后再看看。

11. 46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(),-1);
        backtracking(nums,used);
        return result;
    }

    void backtracking(vector<int>& nums, vector<int> used){
        if(temp.size() == nums.size()){
            result.push_back(temp);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(used[i] == 1){ // has been used in this level
                continue;
            }
            temp.push_back(nums[i]);
            used[i] = used[i] * (-1);
            backtracking(nums,used);
            used[i] = used[i] * (-1);
            temp.pop_back();
        }
    }
};
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

本题其实相比于上题更简单一些，这里使用一个vector即可实现used的功能，因为nums的个数限定了且比较少，只需要正常的回溯即可,找叶节点。分分钟AC。

12.47.全排列 II

给定一个可包含重复数字的序列 nums
，按任意顺序
返回所有不重复的全排列。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(),-1);
        sort(nums.begin(),nums.end());
        backtracking(nums,used);
        return result;
    }

    void backtracking(vector<int>& nums,vector<int>& used){

        if(temp.size() == nums.size()){
            result.push_back(temp);
            return;
        }
        unordered_set<int> uset; // 保存该层循环中是否使用过
        for(int i = 0; i < nums.size(); i++){
            
            if(used[i] == 1){
                continue;
            }
            if(uset.find(nums[i])!=uset.end()){
                continue;
            }
            temp.push_back(nums[i]);
            used[i] = (-1) * used[i];
            uset.insert(nums[i]);
            backtracking(nums,used);
            used[i] = (-1) * used[i];
            temp.pop_back();
        }
    }
};

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.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] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.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] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

本题相较于上题，增加了集合中的元素可重复的条件，所以本题需要增加的判断为同样是在本层进行去重操作，但是和之前的又有点不太一样，原先的只需要判断和上一个元素是否相等然后跳过，这里由于每次都需要从头开始判断，所以只能用set来存储是否使用过，最终AC。有一个通用的去重方法，这个方法效率比较低，通过分析可以只需要使用一个used数组即可。

13. 各种去重操作的总结

简单总结一下

强调一下，树层去重的话，需要对数组排序！

回溯问题都可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

这块比较抽象，如图：

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

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

这里我觉得结合上代码会更好理解一些，因为所谓的在同一树层上，也就是在一个for循环中，如果candidates[i] == candidates[i - 1]，那么意味着当前元素和前一个元素相同，并且used[i - 1]是同一个树枝公用的，used[i - 1]为false，那么前一个元素没有在该树枝上使用过，那么在当前层for循环中，就必定被使用过了，因为前面没有使用过，当前层for循环的开始位置必定是在i-1及之前的位置，且索引为i的元素必定在索引为i-1的元素之后才会被遍历到，所以就能由此判断是树层还是树枝遍历到了。

此处第5、9、12均可用此方法去重。

如果单层使用set来去重的话：

需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交，能明显发现。确实！！！

原因在**回溯算法：递增子序列 (opens new window)**中也分析过，主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

而使用used数组在时间复杂度上几乎没有额外负担！

使用set去重，不仅时间复杂度高了，空间复杂度也高了，在**本周小结！（回溯算法系列三） (opens new window)**中分析过，组合，子集，排列问题的空间复杂度都是 $O (n)$ ，但如果使用set去重，空间复杂度就变成了 $O(n^2)$ ，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

那有同学可能疑惑用used数组也是占用 $O (n)$ 的空间啊？

used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是 $O (n + n)$ ，最终空间复杂度还是 $O (n)$ 。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/117378?site