回溯思想个人理解:有条件的穷举,当该路径不满足条件后,就回溯,返回到上一步其他的路径查找答案。
例如:22 括号生成,我们可以利用穷举的方法,列出所有的可能情况,然后去掉不满足的情况;那么我们就要思考如何实现穷举呢?
??一般看到穷举,我们似乎可以有点规律的尝试回溯思想,使用递归来实现;然后,考虑去除不满足的情况,可以尝试在递归过程中,避免不满足情况的发生,我们可以利用两个数open,close来记录左右括号出现的次数,close<open ,open<n;
同样的17:电话号码的自由组合,也是一个需要穷举的题目,并且可以尝试使用回溯思想去完成;
??当我们选择一个号码后,就会有对应的几种字母出现,这个我们可以利用哈希表来得到结果;然后我们可以根据字母个数,画出不同的路径,任意一条路径下,选择了一个字母后,再选择下一个数字对应的某一个字母;
??边界条件:当我们用来存储字符串的string大小==n*2时,说明可以返回了;
回溯、dfs、递归之间的区别?
递归:就是自我调用,是一种方式,也是一种思想;
dfs:深度优先搜索,先往一个方向搜索到底,然后回升
回溯:是一种思想,就是搜索所有的可能,一旦出现不满足的情况,就回溯;可以说是隐式树的dfs