leetcode 回溯算法

回溯算法

回溯算法使用DFS在解空间中进行搜索，在某条路径上搜索不到答案时，回退到上层，换条路径搜索。c++

• 本质上，回溯就是穷举全部可能，在不可达的时候进行剪枝
• 注意：因为使用递归，可能会致使爆栈

算法框架

backtrace(解空间和路径等状态){
	if(知足退出条件){
		记录知足条件的路径
		return;
	}
	for(在解空间中遍历当前节点){
		//减枝
		if(不可达路径) continue;
		把当前节点加入路径
		backtrace(下次运行的解空间和路径等状态);
		把当前节点从路径中删除
	}
}

题目及分析

leetcode 17 电话号码的字母组合
leetcode 22 括号生成
leetcode 37 解数独
leetcode 93 复原ip地址
leetcode 216 组合总和
leetcode 357 计算各个位数不一样的数字个数
leetcode 526优美的数列web