回溯算法93|78|90
93复原IP地址
class Solution: def __init__(self): self.cut_s = "" self.result = [] self.dot_num = 0 def isValid(self, sub_s): if not sub_s: return False if sub_s[0] == "0" and len(sub_s) > 1: return False if int(sub_s) > 255: return False for item in sub_s: if ord(item) > ord("9") or ord(item) < ord("0"): return False return True def restoreIpAddresses(self, s: str) -> List[str]: self.backTracking(s, 0) return self.result def backTracking(self, s, start_index) -> List: if self.dot_num == 3: sub_s = s[start_index:] if self.isValid(sub_s): self.result.append(self.cut_s + sub_s) return for i in range(start_index + 1, len(s) + 1): sub_s = s[start_index:i] if not self.isValid(sub_s): continue if self.isValid(sub_s): self.cut_s = self.cut_s + sub_s + "." self.dot_num += 1 self.backTracking(s, i) self.cut_s = self.cut_s[:-(len(sub_s) + 1)] self.dot_num -= 1
78子集
class Solution: def __init__(self): self.path = [] self.result = [] def subsets(self, nums: List[int]) -> List[List[int]]: self.backTracking(nums, 0) return self.result def backTracking(self, nums, start_index) -> List: self.result.append(self.path[:]) for i in range(start_index, len(nums)): self.path.append(nums[i]) self.backTracking(nums, i + 1) self.path.pop()
90子集II
class Solution: def __init__(self): self.path = [] self.result = [] def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() used = [0] * len(nums) self.backTracking(nums, 0, used) return self.result def backTracking(self, nums, start_index, used): self.result.append(self.path[:]) for i in range(start_index, len(nums)): if i > start_index and nums[i] == nums[i - 1] and used[i - 1] == 0: continue self.path.append(nums[i]) used[i] = 1 self.backTracking(nums, i + 1, used) self.path.pop() used[i] = 0