day21-数据结构力扣
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[i+1],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:i+1] # 验证规则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/20
if 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