回溯是递归+剪枝，排列组合子集问题的一网打尽之法
回溯（Backtracking）是一种通过递归探索所有可能解的算法，在发现当前路径不可能得到有效解时"回溯"到上一个选择点，尝试其他选项。回溯本质上是带剪枝的 DFS，是解决排列、组合、子集、棋盘问题的万能方法。
def backtrack(路径, 选择列表):
# 1. 结束条件
if 满足条件:
result.append(路径.copy()) # 注意copy!
return
# 2. 遍历选择
for i, 选择 in enumerate(选择列表):
# 2a. 剪枝（可选）
if 不满足条件:
continue
# 2b. 做选择
路径.append(选择)
# 2c. 递归
backtrack(路径, 新选择列表)
# 2d. 撤销选择（回溯）
路径.pop()| 问题类型 | 选择列表 | 去重方式 | 示例 |
|---|---|---|---|
| 子集 | i 之后的所有元素 | 排序 + i > start and nums[i]==nums[i-1] | LC 78 |
| 组合 | i 之后的所有元素 | 同上 + 剩余不够时剪枝 | LC 39, 77 |
| 排列 | 所有未使用的元素 | 排序 + used数组 或 交换 | LC 46, 47 |
题目描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:]) # 注意拷贝!
return
for i in range(len(nums)):
if used[i]:
continue
path.append(nums[i])
used[i] = True
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result时间复杂度：O(n × n!) — n! 种排列，每种拷贝 O(n)
空间复杂度：O(n) — 递归深度 + used 数组
题目描述：给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(start, path):
result.append(path[:]) # 每个节点都是子集
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # 从i+1开始，不回头
path.pop()
backtrack(0, [])
return result时间复杂度：O(n × 2ⁿ) — 2ⁿ 个子集，每个拷贝 O(n)
空间复杂度：O(n)
题目描述：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。candidates 中的数字可以无限制重复被选取。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort() # 排序便于剪枝
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # 剪枝：排序后后面更大
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i而非i+1，可重复选
path.pop()
backtrack(0, [], target)
return result时间复杂度：O(2ⁿ) — 最坏情况所有组合
空间复杂度：O(target/min_val) — 递归深度