算法D27｜回溯算法4｜ 93.复原IP地址 78.子集 90.子集II

本期本来是很有难度的，不过 大家做完 分割回文串 之后，本题就容易很多了 

题目链接/文章讲解：代码随想录

视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili

Python:

class Solution:def __init__(self):self.result = []self.path = []def isvalid(self, s, start, end):if start>end: return Falseif s[start]=="0" and start!=end: return Falsereturn 0<=int(s[start:end+1])<=255def backtracking(self, s, start_index):if len(self.path)==4 and start_index==len(s):addr = ".".join(self.path)self.result.append(addr)returnif len(self.path) > 4: returnfor i in range(start_index, min(start_index+3, len(s))):if self.isvalid(s, start_index, i):self.path.append(s[start_index:i+1])               self.backtracking(s, i+1)self.path.pop()returndef restoreIpAddresses(self, s: str) -> List[str]:if len(s)<4 or len(s)>12: return []self.backtracking(s, 0)return self.result

C++:

C++版本写成直接在string里insert更简洁一些，C++没有类似python string.join的写法。

class Solution {
public:vector<string> result;void backtracking(string& s, int startIndex, int pointNum) {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, '.');backtracking(s, i + 2, pointNum+1);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 (int i=start; 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;}vector<string> restoreIpAddresses(string s) {result.clear();if (s.size()<4 || s.size()>12) return result;backtracking(s, 0, 0);return result;}
};

78.子集  

子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。 

题目链接/文章讲解：代码随想录

视频讲解：回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集_哔哩哔哩_bilibili

本题比较简单

Python：

class Solution:def __init__(self):self.result = []self.path = []def backtracking(self, nums, start_index):self.result.append(self.path[:])for i in range(start_index, len(nums)):self.path.append(nums[i])self.backtracking(nums, i+1)self.path.pop()returndef subsets(self, nums: List[int]) -> List[List[int]]:self.backtracking(nums, 0)return self.result

C++:

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

90.子集II 

大家之前做了 40.组合总和II 和 78.子集 ，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。 

题目链接/文章讲解：代码随想录

视频讲解：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II_哔哩哔哩_bilibili

和上一题类似，区别在于去重，去重部分和40.组合总和II 类似。

Python:

class Solution:def __init__(self):self.result = []self.path = []def backtracking(self, nums, start_index):self.result.append(self.path[:])        for i in range(start_index, len(nums)):if i>start_index and nums[i]==nums[i-1]: continue # 去重self.path.append(nums[i])self.backtracking(nums, i+1)self.path.pop()returndef subsetsWithDup(self, nums: List[int]) -> List[List[int]]:nums.sort()self.backtracking(nums, 0)return self.result

C++:

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