day28 复原IP地址 子集 子集Ⅱ

题目1：93 复原IP地址

题目链接：93 复原IP地址

题意

有效IP地址由4个整数（0~255之间）组成，整数之间用'.'分割? ?给定一个只包含数字的字符串，返回所有可能的有效IP地址

回溯

回溯三部曲：

1）参数和返回值

2）终止条件

3）单层搜索逻辑

代码

class Solution {
public:
    bool isvalid(string& s,int start,int end){
        if(start>end) return false;
        if(s[start]=='0' && start!=end) return false;//以0开头
        int num = 0;
        for(int i=start;i<=end;i++){
            if(s[i]>'9'||s[i]<'0') return false;//不是数字字符
            num = num * 10 + (s[i] - '0');
            if(num > 255) return false;
        }
        return true;
    }
    vector<string> result;
    void backtracking(string& s,int startIndex,int pointsum){
        //终止条件   .的数量是3个时，终止
        if(pointsum==3){
            //判断第3个.之后的字段是否有效
            if(isvalid(s,startIndex,s.size()-1)){
                result.push_back(s);
                return;
            }
        }
        //单层递归逻辑
        for(int i=startIndex;i<s.size();i++){
            if(isvalid(s,startIndex,i)){
                s.insert(s.begin()+i+1,'.');
                pointsum += 1;
                backtracking(s,i+2,pointsum);//递归
                s.erase(s.begin()+i+1);
                pointsum -= 1;
            }
            else break;
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtracking(s,0,0);
        return result;
    }
};

• 时间复杂度: O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
• 空间复杂度: O(n)

题目2：78 子集

题目链接：78 子集

题意

数组中的元素各不相同，返回数组中所有可能的子集，各个子集不重复，每一个子集都是一个组合

回溯

回溯三部曲：

1）参数和返回值

2）终止条件

3）单层递归逻辑

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums,int startIndex){
        result.push_back(path);//每次递归都要收集结果
        //终止条件
        if(startIndex==nums.size()) return;
        //单层递归逻辑
        for(int i=startIndex;i<nums.size();i++){
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

• 时间复杂度: O(n * 2^n)
• 空间复杂度: O(n)

题目3：90 子集Ⅱ

题目链接：90 子集Ⅱ

题意

整数数组nums中可能包含重复元素，返回所有可能子集，各个子集不重复

本题主要是去重操作? ?根据以前的做题经验，使用used数组进行去重

回溯

回溯三部曲：

1）参数和返回值

2）终止条件

3）单层搜索逻辑

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums,int startIndex,vector<bool>& used){
        result.push_back(path);
        //终止条件
        if(startIndex==nums.size()) return;
        //单层搜索逻辑
        for(int i=startIndex;i<nums.size();i++){
            if(i>0 && used[i-1]==false && nums[i]==nums[i-1]) continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums,i+1,used);//递归
            path.pop_back();//回溯
            used[i] = false;//回溯
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtracking(nums,0,used);
        return result;
    }
};

• 时间复杂度: O(n * 2^n)
• 空间复杂度: O(n)