Skip to main content

回溯算法

回溯算法套路​

回溯算法本身就是一个决策树的遍历过程, 或者说是一个**深度优先遍历(DFS)**的过程.

  • 路径

  • 选择列表

  • 结束条件

const result = []

function dfs(路径, 选择列表) {
  if (满足结束条件) {
    result.add(路径)
    return
  }

  for (选择 in 选择列表) {
    做选择
    dfs(路径, 选择列表)
    撤销选择
  }
}

小技巧​

  • 如果给的数组里有重复元素: 得用上 visited 辅助数组
  • 解集不能包含重复的组合: 即 [1, 2] 和 [2, 1] 视为同一种情况, dfs 函数第一个参数传 begin
  • 求子集: dfs 函数第一个参数传 begin, 并且递归时 dfs(i + 1, track)

相关题目​

参考​