代码随想录算法训练营day 28| 第七章 回溯part05 |93.复原IP地址 | 78.子集 | 90.子集II

本文主要是介绍代码随想录算法训练营day 28| 第七章 回溯part05 |93.复原IP地址 | 78.子集 | 90.子集II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93.复原IP地址

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor 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, i+1, path, results)path.pop()def is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = int(s[start:end+1])return 0 <= num <= 255

 78. 子集

class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集，要放在终止添加的上面，否则会漏掉自己# if startIndex >= len(nums):  # 终止条件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop(

 【思考】每一条路径都被记录，不需要终止条件，简单题。

90. 子集2

class Solution:

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

        result = []

        used = [False] * len(nums)

        nums.sort()

        self.backtracking(nums, [], 0, result, used)

        return result

    def backtracking(self, nums, path, start_index, result, used):

        result.append(path[:])

        for i in range(start_index, len(nums)):

            if i> 0 and nums[i] == nums[i-1] and not used[i-1]:

                continue

            path.append(nums[i])

            used[i] = True

            self.backtracking(nums, path, i+1, result, used)

            path.pop()

            used[i] = False

【思考】本题和组合2异曲同工，用used去重。

这篇关于代码随想录算法训练营day 28| 第七章 回溯part05 |93.复原IP地址 | 78.子集 | 90.子集II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---