代码随想训练营第二十八天（Python）｜ 93.复原IP地址 、 78.子集、 90.子集II

93.复原IP地址
1、方法一

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.tracebacking(s, 0, [], res)
        return res

    def tracebacking(self, s, start, path, res):
        if start == len(s) and len(path) == 4: # 刚好分割为 4 份
            res.append(".".join(path[:]))
            return

        if len(path) > 4: # 剪枝
            return

        for i in range(start, len(s)):
            if self.isValidIp(s, start, i):
                path.append(s[start:i+1])
                self.tracebacking(s, i+1, path, res)
                path.pop()

    def isValidIp(self, s, start, end): # 判断是否合法
        if start > end:
            return False
        for i in range(start, end+1):
            if not s[i].isdigit():
                return False
        if int(s[start]) == 0 and start != end:
            return False
        return 0<=int(s[start:end+1])<=255

2、方法二

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.tracebacking(s, 0, 0, [], res)
        return res

    def tracebacking(self, s, start, point, path, res):
        if point == 3:
            if self.isValidIp(s, start, len(s)-1):
                path.append(s[start:])
                res.append("".join(path[:]))
                # 回溯，这里容易忘记
                path.pop() 
            return

        for i in range(start, len(s)):
            if self.isValidIp(s, start, i):
                sub = s[start:i+1]
                path.append(sub)
                path.append(".")
                point += 1 
                self.tracebacking(s, i+1, point, path, res)
                # 回溯
                point -= 1
                path.pop()
                path.pop()


    def isValidIp(self, s, start, end): # 判断是否合法
        if start > end:
            return False
        for i in range(start, end+1):
            if not s[i].isdigit():
                return False
        if int(s[start]) == 0 and start != end:
            return False
        return 0<=int(s[start:end+1])<=255

78.子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.tracebacking(nums, 0, [], res)
        return res

    def tracebacking(self, nums, start, path, res):
        res.append(path[:])
        if start > len(nums)-1:
            return
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            self.tracebacking(nums, i+1, path, res)
            path.pop()

90.子集II

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        self.tracebacking(nums, 0, [], res)
        return res

    def tracebacking(self, nums, start, path, res):
        res.append(path[:])
        if start > len(nums) - 1:
            return

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            self.tracebacking(nums, i+1, path, res)
            path.pop()