93. 复原 IP 地址

分成四份

class Solution {
public:
    // 将字符串分割成4份，每份都是0~255，数字不能含有前导零
    vector<string> res;
    string s;
    vector<string> restoreIpAddresses(string s) {
        this->s = s;
        vector<string> vec;
        dfs(vec, 0);
        return res;
    }

    // tmp划分数组, u下标
    void dfs(vector<string>& tmp, int u)
    {
        if (tmp.size() > 4) return;
        if (u == s.size() && tmp.size() == 4)
        {
            string t;
            for (const auto &it : tmp)
                t += it + ".";
            t.pop_back();
            res.push_back(t);
            return;
        }

        // u是还没选
        for (int i = u; i < s.size(); i ++)
        {
            string t = s.substr(u, i - u + 1);
            if (check(t))
            {
                tmp.push_back(t);
                dfs(tmp, i + 1);
                tmp.pop_back();
            }
            else
                break;
        }
    }

    // 0~255，数字不能含有前导零
    bool check(string s)
    {
        if (s.size() > 1 && s[0] == '0') return false;
        int num = stoi(s);
        if (num > 255) return false;
        return true;
    }
};

78. 子集

加答案有了种新的写法，原来是两个dfs，长度到了就加下答案。

可以只要一个dfs【选】，每次开始都加答案

class Solution {
public:
    vector<int> nums;
    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        this->nums = nums;
        vector<int> tmp;
        dfs(tmp, 0);
        return res;
    }

    void dfs(vector<int>& tmp, int u)
    {
        res.push_back(tmp);
        for (int i = u; i < nums.size(); i ++)
        {
            tmp.push_back(nums[i]);
            dfs(tmp, i + 1);
            tmp.pop_back();
        }
    }
};

90. 子集 II

主打一个去重，和第 40 题一个思路，循环那里玩出花

class Solution {
public:
    // sort之后  和前面的比较, 去重
    vector<vector<int>> res;
    vector<int> nums;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        this->nums = nums;
        vector<int> vec;
        dfs(vec, 0);
        return res;
    }

    // 需要去重
    void dfs(vector<int>& vec, int u)
    {
        res.push_back(vec); // 当前下标u,后面都不选也是一种情况
        // 这里的 i 是会产生距离的
        for (int i = u; i < nums.size(); i ++)
        {
            if (i > u && nums[i] == nums[i-1]) continue;
            vec.push_back(nums[i]);
            dfs(vec, i + 1);
            vec.pop_back();
        }
    }
};