代码随想录｜Day24｜回溯04｜93.复原IP地址、78.子集、90.子集II

93.复原IP地址

本题和 131.分割回文串 一样是一个切割问题，我们使用回溯来遍历所有情况，然后判断IP是否合法。

回溯的一些注意点：

• 终止条件：本题要求向 s 中插入分隔符，意味着所有的数字都必须使用，我们必须遍历完 整个s。另外，合法的IP地址必须由4个整数组成。因此，如果已经遍历完字符串，并且路径中有4个部分，说明找到了一个可能有效的IP地址。
• 剪枝：如果路径长度超过4，说明是非法IP地址。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 判断地址中的整数是否合法
        # 1. 整数的长度超过3
        # 2. 以0开头的非0整数
        # 3. 0-255之外的整数
        def isValid(segment):
            if len(segment) > 3:
                return False
            if int(segment[0]) == 0 and len(segment) > 1:
                return False
            if not 0 <= int(segment) <= 255:
                return False
            return True
        
        def backtrack(startIndex, path):
            # 递归终止条件
            if len(path) == 4 and startIndex == len(s):
                result.append('.'.join(path))
                return
            # 剪枝
            if len(path) > 4:
                return
            # 每个整数的表示：s[startIndex: i + 1]
            # i + 1由于python左闭右开
            for i in range(startIndex, len(s)):
                # 判断每个整数是否符合条件
                # 不符合直接舍弃，符合则继续递归
                if isValid(s[startIndex: i + 1]):
                    path.append(s[startIndex: i + 1])
                    backtrack(i + 1, path)
                    path.pop()
        result = []
        backtrack(startIndex = 0, path = [])
        return result

78.子集

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def backtrack(startIndex, path):
            # 并不是在叶子结点（递归终止处）收集结果
            if startIndex == len(nums):
                return
            # 此递归终止条件可以不写
            # 因为本题需要收集所有的节点，且对结果没有任何限制
            # 当到达叶子结点时，for循环不会执行
            # 因此也不需要剪枝

            for i in range(startIndex, len(nums)):
                path.append(nums[i])
                result.append(path[:])  # 收集每个节点
                backtrack(i + 1, path)
                path.pop()
        # 空集是任何集合的子集
        result = [[]]
        backtrack(startIndex = 0, path = [])
        return result

90.子集II

本题是 40.组合总和II 和 上一题 78.子集 的结合。如果集合中出现重复元素，则需要进行 树层去重。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        
        def backtrack(startIndex, path):

            if startIndex == len(nums):
                return

            for i in range(startIndex, len(nums)):
                # 树层去重
                if i > startIndex and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                result.append(path[:])
                backtrack(i + 1, path)
                path.pop()
        
        result = [[]]
        # 树层去重一定要排序
        nums.sort()
        backtrack(startIndex = 0, path = [])
        return result