Backtracking / BFS / DFS
Overview
DFS/BFS/Backtracking 作为一种暴力搜索手段，时常作为DP找不到公式的下位替代，主要难点在于如何优化。
Subsets & Permutations & Combinations
在解决permutation问题时， 除了用used来记录是否使用过，也可以用List的contains函数（虽然慢点）。
Permutation II 问题，可以先排序然后对每个结果toString做一个pattern看是否生成过，不过也可以用像subset II 一样做一个判断。
需要注意的是，在递归函数中，将tempList添加入结果的ArrayList，需要创建一个新的对象。如果直接添加，使用的是原对象的reference，而我们需要deep copy。
优化（结合记忆化 or DP）
- Word break
- Word break II *
- DFS with Memo
- Trie
需要注意的是，这系列问题需要考虑时间复杂度的问题，可以结合动态规划或者带记忆化的递归解决。
在Word break中，有个小技巧是使用了Boolean object 而不是原生的boolean来作为visited array，因为两者的初始值不同（Boolean null while boolean false）
结合String
String类型的有两个需要考虑的：一个是可以利用Java String immutable的特性直接带入，另一个是如果还是类比于list用StringBuilder的话删除是sb.setLength(sb.length() - 1)
- Generate parentheses
- 用两个变量记录左括号和右括号的个数带入递归真的方便很多=。=
- Letter combinations of a phone number
- Regular Expression Matching *
- Strobogrammatic Number II
- Strobogrammatic Number III
- Word Ladder
- 用一个hashmap来存neighborhood
- Word Ladder II
结合Graph
在Word search中，可以使用亦或操作（bit mask）来避免使用额外的空间（vistied记录是否已经访问）。使用Bit mask使原来图上的数字变成一个非字符，调用完毕后再使用一次^=操作使其还原。Word search II 中使用了trie（字典树），相比于使用hashset + stringbuilder的方法，更加节省时间。