回溯算法,死抓三点
选择
在这里,每次最多两个选择,选左括号或右括号,“选择”会展开出一棵解的空间树。
用 DFS 遍历这棵树,找出所有的解,这个过程叫回溯。
约束条件
即,什么情况下可以选左括号,什么情况下可以选右括号。
利用约束做“剪枝”,即,去掉不会产生解的选项,即,剪去不会通往合法解的分支。
比如(),现在左右括号各剩一个,再选)就成了()),不能让这个错的选择成为选项(不落入递归):
目标
构建出一个用尽 n 对括号的合法括号串。
意味着,当构建的长度达到 2*n,就可以结束递归(不用继续选了)。
网友评论