本文主要是介绍【代码随想录训练营】【Day 30】【回溯-4】| Leetcode 93, 78, 90，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【代码随想录训练营】【Day 30】【回溯-4】| Leetcode 93, 78, 90
需强化知识点
题目
93. 复原 IP 地址
- 分割问题：注意终止条件，要加path长度的限制
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:def isRight(select):if len(select) > 3:return Falseif len(select) > 1 and select[0] == '0':return Falseif int(select) > 255:return Falsereturn Truedef backtracking(s, path, result, startIndex):if len(path) > 4:returnif startIndex == len(s) and len(path) == 4:result.append(".".join(path))returnfor i in range(startIndex, len(s)):select = s[startIndex: i+1]if isRight(select):path.append(select)backtracking(s, path, result, i+1)path.pop()result = []backtracking(s, [], result, 0)return result78. 子集
- 子集问题：result加path的时候不加限制
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:def backtracking(nums, startIndex, path, result):result.append(path[:])for i in range(startIndex, len(nums)):path.append(nums[i])backtracking(nums, i+1, path, result)path.pop()result = []backtracking(nums, 0, [], result)return result
90. 子集 II
- 去重：横向遍历利用startIndex去重
class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:def backtracking(nums, path, result, startIndex):result.append(path[:])for i in range(startIndex, len(nums)):if i > startIndex and nums[i] == nums[i-1]:continuepath.append(nums[i])backtracking(nums, path, result, i+1)path.pop()nums.sort()result = []backtracking(nums, [], result, 0)return result这篇关于【代码随想录训练营】【Day 30】【回溯-4】| Leetcode 93, 78, 90的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
