[算法训练营] 回溯算法专题(二)

🕺作者： 主页

我的专栏
C语言从0到1
探秘C++
数据结构从0到1
探秘Linux
菜鸟刷题集

😘欢迎关注：👍点赞🙌收藏✍️留言

🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

前言

本篇共5题，附有解题思路和AC代码。

边听歌边刷起来吧~

🎸Make Believe

93. 复原 IP 地址

链接：93. 复原 IP 地址

解题思路

1. travalBack 函数是递归函数，用于遍历字符串 s 中可能的 IP 地址组合。它有三个参数：staticIndec 表示当前小节的起始位置，dotCount 表示已经添加的逗号数量。

2. 当 dotCount 等于 3 时，说明已经添加了三个逗号，此时可以判断第三个逗号后面的字符组成的字符串是否满足 IP 地址的要求。如果满足，则将该情况存入 res 中。

3. 在 travalBack 函数中使用循环来遍历从 staticIndec 开始到字符串末尾的位置。对于每一个位置 i，判断从 staticIndec 到 i 组成的小节是否满足 IP 地址的要求。

4. 如果满足条件，则在 s 中插入逗号，并递归调用 travalBack 函数，同时更新 staticIndec 为 i+2，dotCount 加 1，表示处理下一个小节。

5. 在递归调用结束后，需要将插入的逗号删除，以便进行下一次循环。

6. isIPmember 函数用于判断一个字符串是否满足 IP 地址的要求。它将字符串转换为整数，并进行一系列的判断条件，包括长度不为 1 且以 0 开头、只包含数字字符等。

7. 在 restoreIpAddresses 函数中，首先对输入字符串 s 的长度进行判断，如果小于 4 或大于 12，则直接返回空结果。然后调用 travalBack 函数开始递归遍历。

8. 最终返回存储所有满足条件的 IP 地址组合的 res。

AC代码

class Solution {
public:
    vector res;
    //staticIndec是这小节的开始，dotCount是添加逗号的数量
    void travalBack(string& s,int staticIndec,int dotCount)
    {
        if(dotCount==3){//如果添加的逗号的数量等于3了就可以判断第三个逗号后面的字符组成的字符串是否满足条件，满足就把这一种情况存到res中。
            if(isIPmember(s,staticIndec,s.size()-1))res.push_back(s);
            return;
        }

        for(int i=staticIndec;i'9'||str[i]<'0'){
                return false;
            }
        }
        if(str=="")return false;
        if(stoll(str)>255)return false;
        return true;
    }
    vector restoreIpAddresses(string s) {
        if(s.size()<4||s.size()>12)return res;
        travalBack(s,0,0);
        return res;
    }
};
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

78. 子集

链接：78. 子集

解题思路

• 终止条件：不需要写出来因为当staticIndex>nums.size()时，循环已经终止了

• for循环内：在进入下一个节点前先将自己这个节点载入path中，出来时就删去

• 可以看作是二叉树的前序遍历

AC代码

class Solution {
public:
    vector> res;
    vector path;
    void travalBack(vector& nums,int staticIndex)
    {
        res.push_back(path);

        for(int i=staticIndex;i> subsets(vector& nums) {
        travalBack(nums,0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

90. 子集 II

链接：90. 子集 II

解题思路

• 在求组合三的时候讲过解题思路，这题也是类似的参看《[算法训练营] 回溯算法专题(一)》

AC代码

class Solution {
public:
    vector> res;
    vector path;
    void travalBack(vector& nums,int staticIndex,vector used)
    {
        res.push_back(path);

        for(int i=staticIndex;i0&&nums[i]==nums[i-1]&&used[i-1]==false)
            {
                continue;
            }
            else{
                path.push_back(nums[i]);
                used[i]=true;
                travalBack(nums,i+1,used);
                used[i]=false;
                path.pop_back();
            }
        }
    }
    vector> subsetsWithDup(vector& nums) {
        sort(nums.begin(),nums.end());
        vector used(nums.size(),false);
        travalBack(nums,0,used);
        return res;
    }
};
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

491. 递增子序列

链接：491. 递增子序列

解题思路

• 终止条件：当path长度大于2时都可以保留，但是和之前不同在于不需要return，如果return会导致只有长度为2的path

• 这题需要去重但是不能使用排序，因为题目要求是原数组的递增子序列

• 在判断是否能够加入当前数字时的条件是：

  • 如果当前的path不为空，那么前一个值必须比后一个值小，否则跳过

  • 还有就是当前的值是否“用过”，这里需要注意一个点，在for循环之前要使用一个set来记录元素是否使用过，如果使用过就要跳过，避免重复

AC代码

class Solution {
public:
    vector> res;
    vector path;
    void travalBack(vector& nums,int staticIndex)
    {
        if(path.size()>=2){
            res.push_back(path);
        }
        unordered_set umap;
        for(int i=staticIndex;inums[i])||umap.find(nums[i])!=umap.end())
            {
                continue;
            }
            else{
                path.push_back(nums[i]);
                umap.insert(nums[i]);
                travalBack(nums,i+1);
                path.pop_back();
            }
        }
    }
    vector> findSubsequences(vector& nums) {
        travalBack(nums,0);
        return res;
    }
};
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

46. 全排列

链接：46. 全排列

解题思路

1. 首先，定义了一个全局变量res，用于存储最终的结果，即全排列的集合。

2. 定义了一个全局变量path，用于存储当前正在生成的一个排列。

3. 定义了一个辅助函数travalBack，用于进行回溯遍历生成全排列。

4. 在travalBack函数中，首先判断当前path的长度是否等于给定数组nums的长度，如果相等，说明已经生成了一个完整的排列，将其加入到res中，并返回。

5. 如果path的长度不等于nums的长度，就需要继续生成排列。通过一个循环遍历nums数组的每一个元素。

6. 在循环中，首先判断当前元素是否已经被使用过，即used[i]是否为true，如果是，则跳过当前元素，继续下一次循环。

7. 如果当前元素没有被使用过，将其加入到path中，将used[i]设置为true表示该元素已经被使用。

8. 然后，递归调用travalBack函数，继续生成下一个元素的排列。

9. 在递归调用结束后，需要将used[i]重新设置为false，表示该元素未被使用。

10. 同时，还需要将path中的最后一个元素移除，以便生成下一个排列。

11. 在permute函数中，首先创建一个大小为nums长度的布尔型数组used，初始值都为false。

12. 然后调用travalBack函数，开始生成全排列。

13. 最后返回得到的全排列结果res。

AC代码

class Solution {
public:
    vector> res;
    vector path;
    //排列和组合不同，它在乎顺序和单次，所以要使用一个数组used来记录是否使用过
    void travalBack(vector&nums ,vector used)
    {
        //判断是否是全排列，即包含所有元素
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i> permute(vector& nums) {
        vector used(nums.size(),false);
        travalBack(nums,used);
        return res;
    }
};
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