本文主要是介绍二刷算法训练营Day28 | 回溯算法(4/6)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
详细布置：
1. 93. 复原 IP 地址
2. 78. 子集
3. 90. 子集 II
详细布置：
1. 93. 复原 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 地址。给定一个只包含数字的字符串
s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在s中插入'.'来形成。你 不能 重新排序或删除s中的任何数字。你可以按 任何 顺序返回答案。
有点类似LC 131，这个切割问题就可以使用回溯搜索法把所有可能性搜出来
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:result = []self.backtracking(s, 0, 0, "", result)return resultdef backtracking(self, s, start_index, point_num, current, result):if point_num == 3: # 逗点数量为3时，分隔结束if self.is_valid(s, start_index, len(s) - 1): # 判断第四段子字符串是否合法current += s[start_index:] # 添加最后一段子字符串result.append(current)returnfor i in range(start_index, len(s)):if self.is_valid(s, start_index, i): # 判断 [start_index, i] 这个区间的子串是否合法sub = s[start_index:i + 1]self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)else:breakdef is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end: # 0开头的数字不合法return Falsenum = 0for i in range(start, end + 1):if not s[i].isdigit(): # 遇到非数字字符不合法return Falsenum = num * 10 + int(s[i])if num > 255: # 如果大于255了不合法return Falsereturn True2. 78. 子集
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
建议：子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:]) # 收集子集，要放在终止添加的上面，否则会漏掉自己# if startIndex >= len(nums): # 终止条件可以不加# returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()3. 90. 子集 II
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
建议：大家之前做了 40.组合总和II 和 78.子集 ，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。
这道题和上一题区别就是集合里有重复元素了，而且求取的子集要去重。
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
class Solution:def subsetsWithDup(self, nums):result = []path = []used = [False] * len(nums)nums.sort() # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:]) # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] == True，说明同一树枝 nums[i - 1] 使用过# used[i - 1] == False，说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.pop()这篇关于二刷算法训练营Day28 | 回溯算法(4/6)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
