Leetcode回溯法四板一解模板

SL_World

发布于 2021-03-17 16:21:22

1.1K0

文章被收录于专栏：XX

文章目录

1 通用回溯法模板

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.重新安排行程(欧拉回路)