回溯模板

从大佬那里学的https://zhuanlan.zhihu.com/p/93530380，再加上自己做题过程中的一些心得

模板伪代码（python看起来简洁一些）

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        剪枝
        做选择
        backtrack(路径, 选择列表)
        撤销选择

需要注意的几点：

java中由于路径通常是引用类型，所以在加入结果集的时候往往需要new一下，以免路径改变时将res里面的元素也一起改变
java/c++中，选择列表往往会通过一个index来代表到了哪个位置，而保持总列表nums的不变性，至于python和js，天生list就是可变的，append和remove并不会造成太大的开销，所以选择列表可以变而不需要index变量记录
总体框架不变，但是有时候for循环可以使用枚举代替（上下左右方向）
去重用Set，不要每次加入前判断list.contains，那样很慢

private List<List<Integer>> res = new ArrayList<>();	//外面一个变量记录结果
public void backtrace(int[] nums, int index, List<Integer> track){
    if (结束条件){
        res.add(new ArrayList<>(track));	//加入结果时要new，否则所有路径变成最后一个的引用
    	return ;
    }
    for (选择 : 选择列表) {
    	//剪枝
    	if (不满足条件) continue;
        //做选择
        track.add(nums[i]);
        //递归
        backtrace(nums, i + 1, track);
        //撤销
        track.remove(track.size() - 1);
    }
}

毋庸赘言，直接结合回溯题目一起看，看几题就明白了

# 力扣, 回溯

文章

102

分类

14

标签

26

关注我

回溯模板

分类

标签云

推荐阅读

推荐阅读

Your browser is out-of-date!