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

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

93.复原IP地址

思路：要建立一个判断子字符串是否合法的函数，判断多种不合法的情况。在回溯函数中，参数除了s,和startindex还需要一个pointNum来记录句点的数量，当句点的数量等于3时，判断最后一个子串是否合法，如果合法就将s输入到result中，本题都是在字符串s的基础上加句点，没有生成新的字符串。如果s的长度小于4或者大于12，直接return result，剪枝。

class Solution {
public:
vector<string> result;bool isValid(string &s,int start,int end){if(start>end){return false;}if(s[start]=='0'&&start!=end)//s不等于字符的'0'{return false;}int num=0;for(int i =start;i<=end;i++){num= num*10+s[i]-'0';if(num>255){return false;}}return true;}void backtracking(string &s,int startindex,int pointNum){//终止条件,句点数为3，且最后一段合法if(pointNum==3){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,'.');pointNum++;backtracking(s,i+2,pointNum);s.erase(s.begin()+i+1);pointNum--;}else{break;}}}vector<string> restoreIpAddresses(string s) {result.clear();if(s.size()<4||s.size()>12){return result;}backtracking(s,0,0);return result;}
};

78.子集

思路：与组合问题、分割问题类似，从整数数组中找到互不相同的不重复子集。

在回溯函数中，先result.push_back(path)，先将子集的元素输入进result，终止条件就是当startindex==nums.size()时返回，在单层逻辑中找寻满足条件的不重复子集。

class Solution {
public:
vector<int> path;
vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex){result.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) {path.clear();result.clear();backtracking(nums,0);return result;}
};

90.子集II

思路：子集II相比于上一题，整数数组中包含重复元素，但子集不能包含重复子集。这个题跟之前做过的一道题思路相像，需要先对nums排序，然后利用used判断继续生成的子集是否为重复子集，如果是重复的直接continue。

class Solution {
public:
vector<int> path;
vector<vector<int>> result;void backtracking(vector<int>&nums,int startindex,vector<bool> used){result.push_back(path);if(startindex==nums.size()){return;}for(int i =startindex;i<nums.size();i++){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();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {path.clear();result.clear();vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};