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

本文主要是介绍代码随想录算法训练营第二十八天|93 复原IP地址、78 子集、90 子集||，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93 复原IP地址

题目链接：复原IP地址

思路

明面上看这是一道分割题目，但是上一次我们说过分割题目和组合题目差不多都是一样的。要确定好数的深度（切割的深度）、要判断切割出的每一个字符字串是否符合题目要求的条件等。

class Solution {
public:vector<string> res;bool isvalid(string &s, int start, int end){if(start>end){return false;}if(s[start] == '0' && start!=end){return false;}int num = 0;for(int i=start; i<=end; i++){if(s[i]<'0' || s[i] >'9'){return false;}num = num*10 +(s[i] - '0');if(num > 255){return false;}}return true;}void backtracking(string s, int startIndex, int pointSum){if(pointSum == 3){if(isvalid(s, startIndex, s.size()-1)){res.push_back(s);return;}return;}for(int i=startIndex; i<s.size()-1; i++){if(isvalid(s, startIndex, i)){s.insert(s.begin()+i+1, '.');pointSum+=1;backtracking(s, i+2, pointSum);s.erase(s.begin()+i+1);pointSum-=1;}}}vector<string> restoreIpAddresses(string s) {if(s.size() < 4 || s.size() > 12){return res;}backtracking(s, 0, 0);return res;}
};

78 子集

题目链接：子集

思路

这道题目和之前的回溯题目相比，还是比较简单的。仔细思考一下，之前我们收割结果时，每个结果的格式都是一样的，所以我们可以弄一个终止条件来卡住那些不满足要求的结果。但是在这道题目中，每一个结果的格式不太一样，有的结果中有两个元素，有的结果中有三个元素等等。所以这道题目没有终止条件，同时每个path中添加一次，那么对应的每个res中也要添加一次。

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

90 子集||

题目链接：子集||

思路

这道题目和上一道题目相比，多了一个去重的要求。之前在做组合的题目时，有一道题目也是需要去重，和这道题目的去重一模一样。所以针对回溯问题的去重操作，可以有针对性的学习下。
还是使用used来记录每个元素的状态，要记住必须的是有序数组。一般的去重发生在数层之间，也就是一个if循环就可以判断出来。

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int startIndex, vector<int> used){for(int i=startIndex; i<nums.size(); i++){if(i>0 && nums[i-1] == nums[i] && used[i-1]==0){continue;}else{used[i] = 1;path.push_back(nums[i]);res.push_back(path);backtracking(nums, i+1, used);used[i] = 0;path.pop_back(); }}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<int> used(nums.size(), 0);sort(nums.begin(), nums.end());res.push_back(path);backtracking(nums, 0, used);return res;}
};