【算法】回溯算法专题① ——子集型回溯 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

总结

回溯算法是一种通过构建所有可能的解决方案，并在发现当前路径无法达到目标时“回退”一步尝试其他可能性的算法技术。
其核心思想是试探性地解决问题，如果发现当前的选择不符合要求，则撤销前面的选择（即回溯），并尝试其它选择。

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢