Skip to content
On this page

回溯算法

  • 回溯出口,剪枝点
  • 当不满足条件,就回溯返回
  • 深度优先遍历 + 状态重置 + 剪枝
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)
        撤销选择

题目

全排列

MIT License.