【代码随想录训练营】【Day 30】【回溯-4】| Leetcode 93, 78, 90

• 分割问题：注意终止条件，要加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 result

• 子集问题：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

• 去重：横向遍历利用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