模板

  1. def backtrack(self, nums: List[int]) -> List[List[int]]:
  2.     """有放回全排列，演示回溯&深度优化搜索模板"""
  3.     res, size = [], len(nums)
  5.     def dfs(depth, path):
  6.         if depth == size:  # 递归终结条件
  7.             res.append(path[:])
  8.             return
  9.         for i in range(size):
  10.             path.append(nums[i])
  11.             dfs(depth + 1, path)
  12.             path.pop()  # 回退
  14.     dfs(0, [])
  15.     return res
  17. if __name__ == '__main__':
  18.     print(backtrack([1, 2, 3]))
  19.     # [[1, 1, 1], [1, 1, 2], [1, 1, 3],..., [3, 3, 2], [3, 3, 3]]

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

题目

排列组合类