93.复原IP地址题目链接93. 复原 IP 地址 - 力扣LeetCode思路我还是去看题解吧越想越晕贴一版我最开始写的错误版本class Solution: def restoreIpAddresses(self, s: str) - List[str]: if not s: return [] res[] self.backtrack(s,[],[]) return res def backtrack(self,string,path,num): if len(path)4: res.append(path[:]) return for i in range(len(string)): num.append(string[i]) print(num) if num[0]0: path..join(num) elif num[0]255: num.pop() path..join(num) else: self.backtrack(string[i1],path)总体来说写的是四面漏风核心规则回顾· 分割为4 段每段数字范围0~255每段不能有前导 0除非段本身就是0字符串只能用原数字不能增删改正确解题思路回溯法递归终止条件分割出4 段有效数字且字符串刚好遍历完递归过程每次截取 1~3 位字符因为 0-255 最多 3 位验证截取的子串是否有效有效则加入路径继续递归剩余字符串回溯撤销当前选择尝试下一种分割方式提交from typing import List class Solution: def restoreIpAddresses(self, s: str) - List[str]: res [] # 边界条件ip地址总长度最小4位最大12位 if len(s) 4 or len(s) 12: return res def backtrack(start: int, path: List[str]): # 终止条件已经分割4段且遍历完所有字符 if len(path) 4: if start len(s): res.append(..join(path)) return # 每段最多取3位数字 for i in range(start, min(start 3, len(s))): sub s[start:i1] # 验证规则1不能有前导0长度1且以0开头 if len(sub) 1 and sub[0] 0: continue # 验证规则2数值在0-255之间 if 0 int(sub) 255: path.append(sub) backtrack(i 1, path) path.pop() # 回溯 backtrack(0, []) return res78.子集题目链接78. 子集 - 力扣LeetCode思路题目要求数组元素互不相同返回所有可能的子集包括空集、全集子集不能重复解题思路回溯每一步可以选当前元素或不选递归遍历所有位置记录路径每次递归都把当前路径加入结果子集包含所有中间状态回溯撤销选择尝试下一个元素提交from typing import List class Solution: def subsets(self, nums: List[int]) - List[List[int]]: res [] def backtrack(start: int, path: List[int]): # 核心所有路径都是子集直接加入结果 res.append(path.copy()) # 从start开始遍历避免重复子集 for i in range(start, len(nums)): path.append(nums[i]) # 选择当前元素 backtrack(i 1, path) # 递归不能重复选自己 path.pop() # 回溯撤销选择 backtrack(0, []) return res原来这就是收集所有子集的代码90.子集II题目链接90. 子集 II - 力扣LeetCode思路感觉是多了一个去重的步骤刚开始加了一句话示例通过15/20if path not in res:然后我看到不通过示例里面有【1,4,4】【4,1,4】这种重复类型的用刚刚那种方法没办法去重顺序问题那我直接先对nums进行排序通过提交class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: res [] nums.sort() def backtrack(start: int, path: List[int]): if path not in res: res.append(path.copy()) # 从start开始遍历避免重复子集 for i in range(start, len(nums)): path.append(nums[i]) # 选择当前元素 backtrack(i 1, path) # 递归不能重复选自己 path.pop() # 回溯撤销选择 backtrack(0, []) return res