DFS Notes

5/9/2018 update
剪枝取决于在哪儿加的。比如generate parenthese
可以在当前node剪枝，一开始就加。也可以剪2次，分别在左右分支加。
--------------------------------------------------------------------------------------------------------------------------
3/27/2018 update

String partition相关的题，每一层生成的是第几个sub string. 记住用string builder.

相关题目：

 Palindrome Partitioning

Expression Add Operators

------------------------------------------------------------------------------------------------------------------------

• 去重复 if (i != startIndex && nums[i] == nums[i-1]) continue 和排序

             Combination Sum II, Permutations II

• 记住要deep copy
• 遇到matrix要考虑记忆visited.
• 如果是helper返回的是boolean， 里面又有for循环 可以用如下模板

            for (TrieNode n: node.children) {
                if( n != null && helper(word, n, index + 1)) return true;
            }
            return false;

• 遇到search word, 需要有一个index来迭代。比如word search, trie tree add and search word. 
• 关于剪枝。如果是search on matrix，helper里面是search的当前char，所以要在for loop外面剪枝。而求方案数, search on tree，每一个方案是在for loop里面，所以剪枝要在里面。
• 判断条件最好是放在循环外面，代码美观些。
• 尽量把树画出来，然后把树的每一层干什么想彻底。
• DFS helper body is root，从当前节点往下探，加结果。默认当前节点结果已经加了。
• 有关string的，可以避免使用index, 传参数的时候用subtring就好了。

           Palindrome Partitioning, Letter Combinations of a Phone Number