立志重刷代码随想录60天冲冲冲！！——第二十四天

93.复原IP地址

class Solution {
public:
    vector<string> res;
    // pointNum 记录“.”的数量，有三个就结束
    void backtracking(string& s, int startIdx, int pointNum) {
        if (pointNum == 3){
            if (isValid(s, startIdx, s.size() - 1)) {
                res.push_back(s);
                return;
            }
            return;
        }

        for (int i = startIdx; i < s.size(); i++) {
            if (isValid(s, startIdx, i) == true) {
                s.insert(s.begin() + i + 1, '.');
                pointNum++;
                backtracking(s, i + 2, pointNum); // 因为有加入“.”!! 需要＋2!!
                pointNum--;
                s.erase(s.begin() + i + 1);
                continue;
            }
            break;
        }
        return;
    }

    bool isValid(string& s, int start, int end) {
        int num = 0;
        if (start > end) return false; // start必须小于end!!必须加!!
        for (int i = start; i <= end; i++) {
            // 1、如果是非数字，不合法
            if (s[i] >= '0' || s[i] <= '9') {
                num = num * 10 + (s[i] - '0');
                if (num > 255) return false; // 2、大于255 不合法
            } else return false;
        }
        // 3、开头是0，且超过两位数，不合法
        if (s[start] == '0' && end - start > 0) return false;
        return true;
    }

    vector<string> restoreIpAddresses(string s) {
        backtracking(s, 0, 0);
        return res;
    }
};

78.子集

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIdx) {
        res.push_back(path); // 需要放在最前面。包括空集
        if (nums.size() == startIdx) {
            return;
        }

        for (int i = startIdx; 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 res;
    }
};

90.子集II

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    

    void backtracking(vector<int>& nums, int startIdx, vector<bool>& used) {
        res.push_back(path);

        for (int i = startIdx; i < nums.size(); i++) {
            // true：在同一树枝中，有重复。允许重复使用。
            // false: 在同一层中，有重复。不允许重复使用。
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
        return;
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 需要先排序!!
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, 0, used);
        return res;
    }
};