回溯算法
- 回溯出口,剪枝点
- 当不满足条件,就回溯返回
- 深度优先遍历 + 状态重置 + 剪枝
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
def backtrack(nums, i):
if i == len(nums):
if 达到 target:
result += 1
return
for op in { +1, -1 }:
选择 op * nums[i]
# 穷举 nums[i + 1] 的选择
backtrack(nums, i + 1)
撤销选择