代码收藏家技术教程 2025-02-08

【算法】回溯算法专题① ——子集型回溯 python

引入

子集 https://leetcode.cn/problems/subsets/description/

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不相同

思路1：

对每一个元素可以考虑选或不选

代码如下（法1）：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)

        def dfs(i):
            if i == n:
                ans.append(path.copy())  # 不copy的话，后续path的值发生变化会影响ans
                return

            # 选
            path.append(nums[i])
            dfs(i + 1)
            path.pop()  # 回溯

            # 不选
            dfs(i + 1)

        dfs(0)
        return ans

思路2：

对答案枚举：
第一个数选谁，第二个数选谁，第三个数选谁，依此类推
通过从小到大确保不重复

code (法2)：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)

        def dfs(i):
            ans.append(path.copy())

            for j in range(i, n): # 枚举选择的数字
                path.append(nums[j])
                dfs(j + 1)
                path.pop()  # 回溯

        dfs(0)
        return ans

变形

子集 https://leetcode.cn/problems/subsets-ii/

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

思路分析：

与之前相比多了重复元素：
在考虑不选的情况时需要判断是否为重复元素

题解code（法1）：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        nums.sort()

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return

            # 选
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

            # 不选
            while i + 1 < n and nums[i + 1] == nums[i]:
                i += 1
            dfs(i + 1)

        dfs(0)
        return ans

法2 code：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        nums.sort()

        def dfs(i):
            ans.append(path.copy())

            for j in range(i, n):
                if j > i and nums[j] == nums[j - 1]:
                    continue
                # 跳过，枚举下一个
                path.append(nums[j])
                dfs(j + 1)
                path.pop()

        dfs(0)
        return ans

实战演练

分割回文串 https://leetcode.cn/problems/palindrome-partitioning/description/

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

思路1：

对每个结束位置考虑选或不选
（可以假设每对相邻字符之间有个逗号，选还是不选）

题解1：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)

        def dfs(i, start):
            # start作为回文子串的开始，i作为子串的结束
            if i == n:
                ans.append(path.copy())
                return

            # 选（把 s[i] 作为子串的最后一个字符）
            temp = s[start : i + 1]
            if temp == temp[::-1]:
                path.append(temp)
                dfs(i + 1, i + 1)
                path.pop()

            # 不选（最后一个必须选，不然有空字符串）
            if i < n - 1:
                dfs(i + 1, start)

        dfs(0, 0)
        return ans

思路2：

枚举子串结束位置

题解2：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            for j in range(i, n):
                temp = s[i : j + 1]
                if temp == temp[::-1]:
                    path.append(temp)
                    dfs(j + 1)
                    path.pop()

        dfs(0)
        return ans