秋招算法备战第28天 | 93.复原IP地址、78.子集、90.子集II

93. 复原 IP 地址 - 力扣（LeetCode）

这个问题可以通过深度优先搜索(DFS)的方法来解决。我们要做的就是在字符串的每个可能位置插入点，然后检查生成的每一部分是否在 0-255 的范围内，以及是否没有前导零（除非这一部分本身就是零）。以下是解决这个问题的 Python 代码示例。

def restoreIpAddresses(s):def dfs(s, part, path, res):if part == 4:if s == "":res.append(path[:-1])returnfor i in range(1, 4):if i <= len(s):if int(s[:i]) <= 255:dfs(s[i:], part + 1, path + s[:i] + ".", res)if s[0] == '0':breakres = []dfs(s, 0, "", res)return res# Test the function
s = "25525511135"
print(restoreIpAddresses(s))

上述代码的运行结果应该是 ['255.255.11.135', '255.255.111.35']，这是字符串 “25525511135” 可能形成的所有有效 IP 地址。

注意，以上代码默认你正在使用 Python 3.如果你正在使用其他语言，转换这段代码时需要保持算法的主体思想不变，但可能需要进行一些语法或者函数的调整。

下面是代码随想录的参考代码

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor i in range(index, min(index + 3, len(s))):if self.is_valid(s, index, i):sub = s[index:i+1]path.append(sub)self.backtracking(s, i+1, path, results)path.pop()def is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = int(s[start:end+1])return 0 <= num <= 255

78. 子集 - 力扣（LeetCode）

这是一个经典的回溯问题。基本思路是，从空子集开始，然后每次向子集中添加一个新的元素，创建一个新的子集，直到所有元素都被考虑过。对于包含n个元素的集合，其幂集包含2^n个元素，因为每个元素都可以在子集中出现或不出现。

在Python中，可以使用深度优先搜索的方式实现。下面是一个可能的解决方案：

def subsets(nums):def backtrack(first = 0, curr = []):# 如果当前组合达到了有效长度if len(curr) == k:output.append(curr[:])returnfor i in range(first, n):# 添加 nums[i] 进入当前组合curr.append(nums[i])# 使用下一个整数来完成组合backtrack(i + 1, curr)# 回溯，移除 nums[i] 从当前组合curr.pop()output = []n = len(nums)for k in range(n + 1):# 对于从0到n个数字的所有可能组合backtrack()return output

这个函数首先定义了一个递归的回溯函数，用于生成所有长度为k的可能组合。然后，函数为每个可能的组合长度（从0到n）调用了回溯函数。在回溯函数中，我们遍历nums中的所有元素，并在每一步中，都将当前元素添加到当前组合中，然后调用回溯函数来完成剩余的组合。最后，我们从当前组合中移除当前元素，以便在下一次迭代中尝试下一个元素。

90. 子集 II - 力扣（LeetCode）

这是一个带有重复元素的子集问题，它可以通过一种叫做"回溯法"的算法来解决。关键是需要在添加子集时检查这个子集是否已经在结果中了。

首先，为了方便比较，我们可以将输入数组排序。然后，我们使用递归函数backtrack来生成所有可能的子集。在backtrack中，我们添加当前的子集到结果中，然后对于当前位置之后的每一个元素，我们尝试把它添加到子集中，并递归调用backtrack。

这里是Python的实现：

def subsetsWithDup(nums):def backtrack(start, end, tmp):res.append(tmp[:])for i in range(start, end):if i > start and nums[i] == nums[i-1]: # 处理重复的元素continuetmp.append(nums[i])backtrack(i + 1, end, tmp)tmp.pop()nums.sort()res = []backtrack(0, len(nums), [])return res

在这个代码中，我们首先对nums进行排序，然后定义了回溯函数backtrack，最后调用了backtrack来生成所有的子集。在backtrack中，首先我们添加了当前的子集到结果中，然后从start位置开始，遍历到数组的末尾。对于每一个位置，我们首先检查是否有重复的元素，如果有就跳过。然后我们把当前元素加到当前的子集中，调用backtrack生成包含这个元素的所有子集，然后再把这个元素从子集中移除。通过这种方式，我们能够生成所有的子集，并且避免了重复的子集。

总结

Summary

🔍 93. 复原 IP 地址 - 力扣（LeetCode）
这个问题可以通过深度优先搜索(DFS)的方法来解决。我们要做的就是在字符串的每个可能位置插入点，然后检查生成的每一部分是否在 0-255 的范围内，以及是否没有前导零（除非这一部分本身就是零）。

🔍 78. 子集 - 力扣（LeetCode）
这是一个经典的回溯问题。基本思路是，从空子集开始，然后每次向子集中添加一个新的元素，创建一个新的子集，直到所有元素都被考虑过。对于包含n个元素的集合，其幂集包含2^n个元素，因为每个元素都可以在子集中出现或不出现。在Python中，可以使用深度优先搜索的方式实现。

🔍 90. 子集 II - 力扣（LeetCode）
这是一个带有重复元素的子集问题，它可以通过一种叫做"回溯法"的算法来解决。关键是需要在添加子集时检查这个子集是否已经在结果中了。首先，为了方便比较，我们可以将输入数组排序。然后，我们使用递归函数backtrack来生成所有可能的子集。

Facts

• [💻 Python] 使用深度优先搜索(DFS)的方法来解决复原 IP 地址问题，逐个位置插入点，检查生成的每一部分是否在 0-255 的范围内，且没有前导零（除非该部分本身就是零）。
• [💻 Python] 经典回溯问题，找出集合的所有子集。子集的幂集包含2^n个元素，每个元素可以在子集中出现或不出现。
• [💻 Python] 带有重复元素的子集问题，使用"回溯法"算法解决。需要检查添加的子集是否已经在结果中，可以通过排序数组来避免重复。