算法记录 | Day28 回溯算法

93.复原IP地址

思路：

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• s字符

• startindex（int）为下一层for循环搜索的起始位置。

2.终止条件：当len(path)==4且遍历到字符串最末尾，将path加入res，len(path)>4 return

3.遍历过程：取temp= s[startindex:i+1]，判断是否合法

• 不能超过255
• 0不能为前导
  • 不能为00
  • 不能为非0数字前导，e.g: 011

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res = []path = []def backtrack(s,startindex):if len(path)>4:return if len(path) == 4 and startindex == len(s):res.append(".".join(path))return for i in range(startindex, len(s)):temp = s[startindex:i+1]if int(temp)>255:continueif int(temp) == 0 and i!=startindex:continueif s[startindex]=='0'and int(temp)>0:continuepath.append(temp)backtrack(s,i+1)path.pop()backtrack(s,0)return res

78. 子集

思路:

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• nums数组
• startindex（int）为下一层for循环搜索的起始位置。

2.终止条件：当startindex >len(nums)，完成遍历终止

3.遍历过程：求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

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

90. 子集 II

思路:

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• nums数组
• startindex（int）为下一层for循环搜索的起始位置。

2.终止条件：当startindex >len(nums)，完成遍历终止

3.遍历过程：去重，先对nums排序，for循环层不能使用相同元素，排序数组，判断nums[i]==nums[i-1]

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:res = []path = []nums.sort()def backtrack(nums,startindex):if startindex>len(nums):returnif len(path)<=len(nums):res.append(path[:])for i in range(startindex,len(nums)):if i>startindex and nums[i] ==nums[i-1]:continuepath.append(nums[i])backtrack(nums,i+1)path.pop()backtrack(nums,0)return res