代码随想录算法训练营第二十八天 | 93.复原IP地址、78.子集、90.子集II

93.复原IP地址

题目链接：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 中的任何数字。你可以按 任何 顺序返回答案。

文章讲解/视频讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

思路

这道题和分割回文串有相似之处，同样采用回溯来解决。回溯的横向遍历是确定每层的分隔位置，纵向遍历则是递归地确定下一个分隔的位置。

首先确定回溯函数的参数：代表当前分隔的组合path，当前遍历到的下标starti。

确定结束条件：当starti遍历到字符串s末尾，或组合中的元素个数达到了四个。其中若同时满足这两个条件，将组合中的元素合成一个IP地址，加入结果。

遍历：横向遍历确定每层的分隔位置，纵向遍历则递归地确定下一个分隔的位置。对于每个分隔位置，判断从starti到该位置能否构成一个合法的IP字段，如果是，则可以纵向递归地向下遍历。

C++实现

class Solution {
public:
    vector<string> results;

    vector<string> restoreIpAddresses(string s) {
        vector<string> path;
        backtracing(path, 0, s);
        return results;
    }

    void backtracing(vector<string>& path, int starti, const string& s){
        if(starti == s.size() || path.size() == 4){
            if(starti == s.size() && path.size() == 4){
                string tmp;
                for(int i = 0;i<path.size();i++){
                    tmp += path[i];
                    if(i < path.size() - 1) tmp += ".";
                }
                results.push_back(tmp);
            }
            return;
        }

        for(int j = starti;j<s.size() && j < starti + 3;j++){ // 剪枝
            if(isvalid(s, starti, j)){
                path.push_back(s.substr(starti, j - starti + 1));
                backtracing(path, j + 1, s);
                path.pop_back();
            }
        }
    }

    bool isvalid(const string& s, int left, int right){
        // 判断前导0
        if(s[left] == '0'){
            if(right > left) return false;
        }

        int num = stoi(s.substr(left, right - left + 1));
        return num >= 0 && num <= 255;
    }
};

78.子集

题目链接：78.子集

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

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

文章讲解/视频讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

思路

利用回溯来处理，这里横向遍历是遍历加入当前元素和不加入当前元素两种情况，纵向遍历是递归地寻找下一个元素。

回溯函数的参数：当前已加入的元素集合path，当前遍历到的元素下标starti。

回溯函数的终止条件：很简单，starti等于nums.size()，即遍历到原数组末尾。

回溯函数的遍历：每一层的横向遍历，遍历判断加入当前元素和不加入当前元素两种情况，纵向遍历是递归寻找下一个元素。

看了卡哥的教程之后，知道了原来可以把子集问题想成收集树的所有节点。如下图，相当于在遍历这样一棵树的时候，将节点的值全部存入结果中。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        backtracing(path, 0, nums);
        return results;
    }

    void backtracing(vector<int>& path, int starti, const vector<int>& nums){        
        if(starti == nums.size()){
            results.push_back(path);
            return;
        }
        // 不加入i元素
        backtracing(path, starti + 1, nums);
        // 加入i元素
        path.push_back(nums[starti]);
        backtracing(path, starti + 1, nums);
        path.pop_back();
    }
};

// 另一种思路
class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        backtracing(path, 0, nums);
        return results;
    }

    void backtracing(vector<int>& path, int starti, const vector<int>& nums){   
        results.push_back(path);     
        if(starti == nums.size()){
            return;
        }
        for(int i = starti;i<nums.size();i++){
            path.push_back(nums[i]);
            backtracing(path, i + 1, nums);
            path.pop_back();
        }
    }
};

90.子集II

题目链接：90.子集II

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

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

文章讲解/视频讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html

思路

采用和上题一样的，遍历整棵树，将树的节点存入结果中的思路。本题多了一点，需要去重。

去重的思路：先把原数组nums排好序，然后回溯函数的每一层在遍历时，判断当前遍历的值和上一个遍历的值是否相等，如果相等则跳过。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        backtracing(path, 0, nums);
        return results;
    }

    void backtracing(vector<int>& path, int starti, const vector<int>& nums){
        results.push_back(path);
        if(starti == nums.size()) return;

        for(int i = starti;i<nums.size();i++){
            if(i > starti && nums[i] == nums[i - 1]) continue; // 去重
            path.push_back(nums[i]);
            backtracing(path, i + 1, nums);
            path.pop_back();
        }
    }
};