Leetcode回溯法四板一解模板

2021-03-17 16:21:22 浏览数 (1)

文章目录

    • 1 通用回溯法模板
    • 2 回溯法常用四板斧 一解（first索引 inPath sort相邻去重 set非相邻去重）
    • 附录：本专题刷题列表
    • 致谢

1 通用回溯法模板

代码语言：javascript复制
vector<xxx> solution;
void backtrack(路径, 选择列表){
	if (满足终止条件) {
		添加路径(当前解);
		return;
	}
	for (选择 : 选择列表) {
		if (notValid(选择)) continue;
		做选择;     // 在选择列表中移除<选择>
		backtrack(路径, 选择列表);
		撤销选择;   // 将<选择>恢复到选择列表中
	}
}

2 回溯法常用四板斧 一解（first索引 inPath sort相邻去重 set非相邻去重）

通过经典题目的训练，目前常用在回溯法求解问题的技巧主要有4种，解题时依据问题性质通过混用其中一至多种可实现机械化解题，针对这四种技巧具体介绍如下

四板一解

功能

例子

inPath备忘录(i = 0)

避免重复相同的选择

避免[1,1,1]或[2,2,2]出现

first索引(i = first)

避免重复相同的选择 避免顺序不同，但组合相同的解

避免[1,2,3]和[1,3,2]共现

sort相邻去重!(input[i-1]==input[i])

输入有重复时，避免重复完全相同的解

避免[2,2,3]和[2,2,3]共现

set非相邻去重!set.count(input[i])

输入有重复 不能sort时，避免重复完全相同的解

同上

bool backtrack(args) {}

只返回1个解使用if (backtrack()) return true;

——

【备注】：[1, 2, 3, 2]就可以出现两个路径不同但完全相同的解[2, 3]

上述四板一解在不同题目中的使用情况，具体使用方法直接点击题目链接查看即可

四板斧

适用场景

题目

inPath备忘录(i = 0)

排列

46.全排列; 47.全排列 II

first索引(i = first)

组合/子集/分割

77.组合; 39.组合总和; 216.组合总和III; 78.子集; 131. 分割回文串; 93.复原 IP 地址

sort相邻去重!(input[i-1]==input[i])

输入有重复(辅助上述场景)

90.子集II; 40.组合总和II; 47.全排列 II

set非相邻去重!set.count(input[i])

输入有重复 不能排序

491. 递增子序列

bool backtrack(args) {}

只返回1个解

37. 解数独; 332.重新安排行程

其他方法

适用场景

题目

回溯模板 多条件剪枝

棋盘问题等

51. N皇后; 37. 解数独; 17. 电话号码的字母组合

回溯模板 新数据结构

图论等

332.重新安排行程(欧拉回路)

附录：本专题刷题列表

致谢

感谢「代码随想录」公众号梳理的思路，欢迎大家关注这位大佬的公号

count input set sort

0 人点赞