目录
- 引入
- 变形
- 实战演练
- 总结
引入
子集 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的值发生变化会影响ansreturn# 选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 += 1dfs(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())returnfor 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
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
