代码随想录算法训练营第二十八天|LeetCode93 复原IP地址、LeetCode78 子集

题1：

指路：LeetCode93 复原IP地址

思路与代码：

对于这种暴搜出不来的就该用回溯了。对于一个合理的IP地址：有四个字串，每个字串的值的和在[0, 255]中即可(注意不可有前导0)。所以我们用一个计数器pointSum为给定字符串中分割字串的分隔符'.'计数。每当有一个合理的子串时在该子串后面增加一个分隔符，当pointSum等于3时该字符串合理。

class Solution {private:vector<string> result;void backtracking(string& s, int startIndex, int pointSum) {// pointSum 是IP地址中合理分割的分隔符if (pointSum == 3) {  // 三个分隔符四个部分是正常的IP地址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);  // +2是因为统计分隔符后面的子串s.erase(s.begin() + i + 1);  // 回溯1：删除分隔符pointSum -= 1;  // 回溯2：统计器-1复原}else break;}}// 判断子串是否在[0, 255]范围内bool isValid(const string& s, int begin, int end) {if (begin > end) return false;if (s[begin] == '0' && begin != end) return false;// 有前导0不合法int num = 0;for (int i = begin; 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;}
public:vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return result;     }
};

emm……蛮有难度的一个题。题意很好懂，思路也容易理，但是不大好写，我改了蛮久。

题2：

指路：LeetCode78 子集

思路与代码：

标标准准的回溯题，类似于之前的组合。遇到合理的路径加入最终结果集，回溯弹出即可。代码如下：

class Solution {private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& s, int startIndex) {result.push_back(path);if (path.size() > s.size()) return ;for (int i = startIndex; i < s.size(); i++) {path.push_back(s[i]);backtracking(s, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};