93.复原IP地址

力扣链接
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的IP地址不能含有前导0，共有4个字段，且每个字段不能超过255

思路

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.backtracking(s, 0, 0, "", res)
        return res

    def backtracking(self, s, startIndex, pointNum, cur, res):
        if pointNum == 3: # 句点数量3个时，分割结束
            if self.isLeagal(s, startIndex, len(s)-1):
                cur += s[startIndex:]
                res.append(cur)
            return
        
        for i in range(startIndex, len(s)):
            if self.isLeagal(s ,startIndex, i):
                sub = s[startIndex : i+1]
                self.backtracking(s, i+1, pointNum + 1, cur + sub + '.', res)
            else:
                break

    def isLeagal(self, s, start, end):
        if start > end:
            return False
        if s[start]=='0' and start != end: # 前导0的情况
            return False
        num = 0
        for i in range(start, end+1):
            if not s[i].isdigit(): # 遇到非数字字符不合法
                return False
            num = num*10 + int(s[i])
            if num > 255: # 大于255不合法
                return False
        return True

78.子集

力扣链接
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集，包括空集。

思路

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

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

90.子集II

力扣链接
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

思路

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used = [False] * len(nums)
        nums.sort()
        self.backtracking(nums, 0, used, path, res)
        return res
    def backtracking(self, nums, startIndex, used, path, res):
        res.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]:
                continue
            path.append(nums[i])
            used[i] = True
            self.backtracking(nums, i+1, used, path, res)
            used[i] = False
            path.pop()