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