代码随想录算法训练营 Day 21

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

        # 判断是否合法：1. 长度大于1时，首位数是否为0；2. 数字整体是否大于255；3. 其中是否含有非数字字符（本题中明确规定只含有数字，因此省略）
        def is_valid(substring):
            if len(substring) > 1 and substring[0] == '0':
                return False
            
            if int(substring) > 255:
                return False
            
            return True

        def backtracking(num_part, start, arr):
            if num_part == 4:
                # 整个字符参与划分，即没有剩下的部分
                if start == len(s):
                    res.append('.'.join(arr))
                return
            
            for i in range(start, len(s)):
                substring = s[start:i+1]
                if is_valid(substring):
                    arr.append(substring)
                    num_part += 1
                    backtracking(num_part, i + 1, arr)
                    num_part -= 1
                    arr.pop()
        
        backtracking(0, 0, [])

        return res

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

        def backtracking(start, arr):
            res.append(arr[:])
            
            for i in range(start, len(nums)):
                arr.append(nums[i])
                backtracking(i + 1, arr)
                arr.pop()
        
        backtracking(0, [])

        return res

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []

        nums.sort()
        def backtracking(start, arr):
            res.append(arr[:])

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                    
                arr.append(nums[i])
                backtracking(i + 1, arr)
                arr.pop()
        
        backtracking(0, [])

        return res