93.复原IP地址
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
self.backtracking(s, [], 0, result)
return result
def backtracking(self, s, path, index, result):
if index >= len(s) and len(path) == 4:
result.append('.'.join(path))
return
if len(path) > 4:
return
for i in range(index, min(index+3, len(s))):
if self.is_valid(s, index, i):
sub = s[index:i+1]
path.append(sub)
self.backtracking(s, path, i+1, result)
path.pop()
def is_valid(self, s, start, end):
if start > end:
return False
if s[start] == '0' and start != end:
return False
num = int(s[start:end+1])
return 0 <= num and num <= 255
78.子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = [[]]
self.backtracking(nums, [], 0, result)
return result
def backtracking(self, nums, path, index, result):
if index >= len(nums):
return
for i in range(index, len(nums)):
path.append(nums[i])
result.append(path[:])
self.backtracking(nums, path, i+1, result)
path.pop()
90.子集II
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = [[]]
self.backtracking(nums, [], 0, result)
return result
def backtracking(self, nums, path, index, result):
if index >= len(nums):
return
for i in range(index, len(nums)):
if index != i and nums[i] == nums[i-1]:
continue
path.append(nums[i])
result.append(path[:])
self.backtracking(nums, path, i+1, result)
path.pop()