代码随想录day28 回溯算法逐渐摸到点套路

93.复原IP地址

题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1：

• 输入：s = "25525511135"
• 输出：["255.255.11.135","255.255.111.35"]

思考

这题有点复杂，需要考虑的因素太多了，总的来说还是一个切割问题，还是如何判断切割下来的字符串有效，需要考虑的很多条件，下面先说下大体思路：

1、在回溯函数入参里增加一个参数pointSum，代表目前加了多少个点，中止条件就是当pointSum == 3，同时在res push_back string前，要判断最后那一段的string合不合题意

2、在纵向递归遍历时，也要判断截取的string合不合题意，如果合题意，那么直接在i+1处加.

3、判断字符串合不合题意有三种场景：

• 字符串如果长度大于1，开头是否为零
• 字符串中是否有不在‘0’ - ‘9’里的字符
• 最后截取的字符串转换成数字是否大于255

如果都满足条件，那么这个字符串才合法，才能被存到结果vector里

代码

class Solution {

public:

? ? vector<string> res;

? ? void backTracking(string& s, int startIndex, int pointSum) {

? ? ? ? if(pointSum == 3) {

? ? ? ? ? ? if (isValid(s, startIndex, s.size() -1)) {

? ? ? ? ? ? ? ? res.push_back(s);

? ? ? ? ? ? ? ? return;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? for(int i = startIndex; i < s.size(); i++) {

? ? ? ? ? ? if (isValid(s, startIndex, i)) {

? ? ? ? ? ? ? ? s.insert(s.begin()+i+1, '.');

? ? ? ? ? ? ? ? pointSum++;

? ? ? ? ? ? ? ? backTracking(s, i+2, pointSum);

? ? ? ? ? ? ? ? pointSum--;

? ? ? ? ? ? ? ? s.erase(s.begin() + i + 1);

? ? ? ? ? ? }

? ? ? ? ? ? else break;

? ? ? ? }

? ? }

? ? bool isValid(const string& s, int start, int end) {

? ? ? ? if(start > end) return false;

? ? ? ? if(s[start] == '0' && start != end) return false;

? ? ? ? int num = 0;

? ? ? ? for(auto c : s.substr(start, end - start + 1)) {

? ? ? ? ? ? if(c > '9' || c < '0') return false;

? ? ? ? ? ? num = num*10 + (c - '0');

? ? ? ? ? ? if (num > 255) return false;

? ? ? ? }

? ? ? ? return true;

? ? }

? ? vector<string> restoreIpAddresses(string s) {

? ? ? ? backTracking(s, 0, 0);

? ? ? ? return res;

? ? }

};

78.子集z

题目

给定一组不含重复元素的整数数组?nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [ [3], ? [1], ? [2], ? [1,2,3], ? [1,3], ? [2,3], ? [1,2], ? [] ]

思考

这题其实和组合那题非常像，唯一的区别是，最终结果数组res在每次递归时都要存path，而不能当startIndex == nums.size的时候才存，因为这里对于纵向递归没有任何约束条件，唯一要注意的就是横向遍历时要去重

代码

class Solution {

public:

? ? vector<vector<int>> res;

? ? vector<int> path;

? ? void backTracking(vector<int> nums, int startIndex) {

? ? ? ? res.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();

? ? ? ? }

? ? }

? ? vector<vector<int>> subsets(vector<int>& nums) {

? ? ? ? backTracking(nums, 0);

? ? ? ? return res;

????????}

};

90.子集II

题目

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

• 输入: [1,2,2]
• 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思考

这题可以说和组合总和ii那题一模一样，也是要用到used数组，不同的地方也是和子集i一样，就不过多赘述了

代码

class Solution {

public:

? ? vector<vector<int>> res;

? ? vector<int> path;

? ? void backTracking(vector<int> nums, vector<int> used, int startIndex) {

? ? ? ? res.push_back(path);

? ? ? ? if(path.size() >= nums.size()) return;

? ? ? ? for(int i = startIndex; i < nums.size(); i++) {

? ? ? ? ? ? if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0) continue;

? ? ? ? ? ? path.push_back(nums[i]);

? ? ? ? ? ? used[i] = 1;

? ? ? ? ? ? backTracking(nums, used, i+1);

? ? ? ? ? ? used[i] = 0;

? ? ? ? ? ? path.pop_back();

? ? ? ? }

? ? }

? ? vector<vector<int>> subsetsWithDup(vector<int>& nums) {

? ? ? ? sort(nums.begin(), nums.end());

? ? ? ? vector<int> used(nums.size(), 0);

? ? ? ? backTracking(nums, used, 0);

? ? ? ? return res;

? ? }

};