Python刷题模板——回溯算法

回溯问题:决策树遍历过程

1.路径:已经做出的选择

2.选择列表:当前可以做的选择

3.结束条件:到达决策树底层,无法再做选择的条件

回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作

回溯算法框架

result = []
def backtrack(路径,选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        # 做选择
        从选择列表移除该选择
        路径.add(选择)
        backtrack(路径,选择列表)
        # 撤销选择
        将该选择再加入选择列表

相关问题

46. 全排列

51. N 皇后

排列、组合、子集:用start参数排除已选择的数字

发表评论