代码随想录算法训练营第二十一天 | 回溯算法 Part03

449 字

2 分钟

代码随想录算法训练营第二十一天 | 回溯算法 Part03

2025-07-04

算法

子集问题

/

算法

/

LeetCode

/

Python

子集问题（Subsets）#

子集问题是回溯算法的重要分支，目标是在一个集合中找出所有可能的子集组合。
它与组合、排列不同，强调的是「是否选某个元素」，而非顺序或选多少个。

🔸 考点梳理#

✅ 子集问题本质是二叉决策树的遍历（选 or 不选）。
✅ 去重问题（如子集 II）需要对输入进行排序并跳过重复。
✅ IP 地址拆分本质上也是一种子集划分（分组 + 合法性判断）。

93. 复原 IP 地址#

LeetCode 93. 复原 IP 地址

1
class Solution:
2
    def restoreIpAddresses(self, s: str) -> List[str]:
3
        self.track = []  # 当前存储的 IP 段
4
        self.res = []    # 合法的 IP 结果
5
        self.backtrack(s, 0)
6
        return self.res
7

8
    def backtrack(self, s: str, start: int) -> None:
9
        # 如果遍历完字符串且已构成 4 段，加入结果
10
        if start == len(s) and len(self.track) == 4:
11
            self.res.append('.'.join(self.track))
12
            return
13
        # 剪枝：若已有4段或遍历完
14
        if len(self.track) >= 4:
15
            return
16
        for i in range(start, len(s)):
17
            if not self.isValid(s, start, i):
18
                continue
19
            self.track.append(s[start:i + 1])     # 做选择
20
            self.backtrack(s, i + 1)              # 递归下一段
21
            self.track.pop()                      # 撤销选择
22

23
    def isValid(self, s: str, start: int, end: int) -> bool:
24
        length = end - start + 1
25
        if length == 0 or length > 3:
26
            return False
27
        if length > 1 and s[start] == '0':  # 排除前导 0
28
            return False
29
        if int(s[start:end + 1]) > 255:
30
            return False
31
        return True

78. 子集#

LeetCode 78. 子集

1
class Solution:
2
    def subsets(self, nums: List[int]) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        self.backtrack(nums, 0)
6
        return self.res
7

8
    def backtrack(self, nums, start):
9
        self.res.append(self.path[:])
10
        for i in range(start, len(nums)):
11
            self.path.append(nums[i])
12
            self.backtrack(nums, i + 1)
13
            self.path.pop()

90. 子集 II（含重复元素）#

LeetCode 90. 子集 II

1
class Solution:
2
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        nums.sort()  # 排序后方便跳过重复
6
        self.backtrack(nums, 0)
7
        return self.res
8

9
    def backtrack(self, nums, start):
10
        self.res.append(self.path[:])
11
        for i in range(start, len(nums)):
12
            # 去重核心：同一层中跳过重复元素
13
            if i > start and nums[i] == nums[i - 1]:
14
                continue
15
            self.path.append(nums[i])
16
            self.backtrack(nums, i + 1)
17
            self.path.pop()