回溯算法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
