代码随想录算法训练营第二十四天|leetcode78、90、93题

一、leetcode第93题

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        vector<string> res;

        function<void(string, int, int)> dfs = [&](string ss, int idx, int t) -> void {
            // 终止条件，枚举完，使用了4次`.`，需要删掉一个`.`
            if (idx == n || t == 4) {
                if (idx == n && t == 4) {
                    ss.pop_back();
                    res.push_back(ss);
                }
                return;
            }
            // 枚举位数，从idx下标开始i个位数
            for (int i = 1; i <= 3; ++ i) {
                if (i + idx > n) return;
                if (i != 1 && s[idx] == '0') return;
                if (i == 3 && stoi(s.substr(idx, 3)) > 255) return;
                dfs(ss + s.substr(idx, i) + ".", idx + i, t + 1);
            }
        };
        dfs("", 0, 0);
        return res;
    }
};

二、leetcode第78题

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    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();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

三、leetcode第90题

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    //组合问题设置stratindex：为了防止重复
    //排列问题从0开始
    void dfs(vector<int>&nums,int startindex,vector<bool>&st)
    {
        res.push_back(path);//先加入答案
        if(startindex>=nums.size())
        {
            return;
        }
        for(int i=startindex;i<nums.size();i++)
        {
            //树层去重
            if(i>0&&nums[i-1]==nums[i]&&st[i-1]==false) continue;
            st[i]=true;
            path.push_back(nums[i]);
            dfs(nums,i+1,st);
            st[i]=false;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> st(nums.size(),false);
        sort(nums.begin(),nums.end());
        dfs(nums,0,st);
        return res;
    }
};