算法随想Day25【回溯算法】| LC93-复原IP地址、LC78-子集、LC90-子集Ⅱ

LC93. 复原IP地址

细节太多了（调了不久才调通）：

• 剪纸操作和不合法的直接返回
  • 段位以0为开头的数字不合法
  • 段位如果大于255了不合法
  • 段位里有非正整数字符不合法（但题意说明字符串只包含数字）
• 终止条件的判断：用完s中的全部字符，且dot('.')个数要符合要求
• 开始用s = "10123"来做调试，在判断255那步，直接写了if (str > "255")，很明显有错误，如：对"3"而言。是"3" > "255"的

vector<string> result;
string temp;
int dot_count = 0;
void restoreLoop(string& s, int left)
{
    if (dot_count == 4)
    {
        if (left >= s.size())
        {
            temp.pop_back();  //暂时将最后一个"."弹出，做压出结果集处理
            result.emplace_back(temp);
            temp.push_back('.');  //要重新放回，保证回溯中的循环不变量
        }
        return;
    }
    for (int i = left; i < s.size(); i++)
    {
        string str = s.substr(left, i - left + 1);
        int val = stoi(str);
        ////段位以0为开头的数字不合法，size > 3时做剪枝
        if ((str.size() > 1 && str.front() == '0') || str.size() > 3)
        {
            return;
        }
        if (val > 255)
        {
            return;
        }
        temp += str;
        temp.push_back('.');
        ++dot_count;
        restoreLoop(s, i + 1);
        for (int j = 0; j <= str.size(); ++j)
        {
            temp.pop_back();
        }
        --dot_count;
    }
}
vector<string> restoreIpAddresses(string s)
{
    if (s.size() >= 4 && s.size() <= 12)  //剪枝
    {
       restoreLoop(s, 0);
    }
    return result;
}

LC78. 子集

vector<int> temp;
vector<vector<int>> result;
void subsetsLoop(vector<int>& nums, int index)
{
    if (index <= nums.size())
    {
        result.emplace_back(temp);
        // return;  此处相对于“组合”题目，即不用显式返回
    }
    for (int i = index; i < nums.size(); i++)
    {
        temp.emplace_back(nums[i]);
        subsetsLoop(nums, i + 1);
        temp.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums)
{
    subsetsLoop(nums, 0);
    return result;
}

LC90. 子集Ⅱ

对比了下相对于预期结果少了数组，比如输出中找不到-1和0同时出现的数组

（问题找到：定义prev时，没有初始化，默认值为随即，因此可能会出现异常）

但在VS Code中用这个例子调试时，结果的数组的确是有64项的

int prev;
vector<int> temp;
vector<vector<int>> result;
void subsetsLoop(vector<int>& nums, int index)
{
    if (index <= nums.size())
    {
        result.emplace_back(temp);
        // return;  此处相对于“组合”题目，即不用显式返回
    }
    for (int i = index; i < nums.size(); i++)
    {
        if (i != 0 && nums[i] == prev)
        {
            continue;
        }
        temp.emplace_back(nums[i]);
        subsetsLoop(nums, i + 1);
        prev = temp.back();
        temp.pop_back();
    }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
    sort(nums.begin(), nums.end());
    subsetsLoop(nums, 0);
    return result;
}

根据题意（-10 < nums[i] < 10），将prev的初始值设置为-20，可以通过了