93.复原IP地址
力扣链接
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的IP地址不能含有前导0，共有4个字段，且每个字段不能超过255
思路
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res = []self.backtracking(s, 0, 0, "", res)return resdef 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)returnfor 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:breakdef isLeagal(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 True
78.子集
力扣链接
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集，包括空集。
思路
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []path = []self.backtracking(nums, 0, path, res)return resdef 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 resdef 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]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i+1, used, path, res)used[i] = Falsepath.pop()
