Leetcode 中 DFS 深度优先搜索

DFS常用在求permutation, combination, 找出所有解，Search等等，思想就是把解看做树的叶子然后遍历之。
1. Letter combination of a Phone Number
遇到一个数字，把所有可能的字符试一遍，以此为分叉，看下一个数字。遇到1或者0没有分叉，直接看下一个数字
2. Generate Parentheses
By default 加(直到(用完，当l>n的时候可以加）。 最后缺的）一并补上 3. Next Permutation
严格意义上 Next Permutation不算是DFS，但是他巧妙的利用了DSF不同branch的关系，来更有效的得出结果。
 step 1: find largest k so that num[k]<num[k+1]; if no, this is the last one. the "next" one is the smallest one in lex order. sort the array.
 step 2: find lasgest l so that num[l]>num[k]; and swap.
 step 3: reverse (K+1, end)
3.a 此题的另一个变种是last permutation 思路相似
 step 1: find largest k so that num[k]>num[k+1];
 step 2: find lasgest l so that num[l]<num[k]; and swap. if l=0, this is the first one. the "last" one is the biggest one in lex order. sort the array.
 step 3: reverse (K+1, end)


 4. Sudoku Solver
遍历每个格子，看是否为空，不为空就依次试1-9，检查是否合法，包括行合法，列合法，block合法。不合法就返回，否则继续试下一个格子 5. Combination Sum
这题重点在思路。首先将数字集合排序，从最小的开始依次往后挑，直到sum等于target或者没得挑了退出。 用一个index数组来记录挑到的数字 不用index数组的解法： 6. Combination Sum II
这题思路和上题一样，只不过挑过的数字就不能再挑了，i=index[n]改为i=index[n]+1 不用index数组的做法也和上题一样，把foo的实参之一i改为i＋1.同时需要注意去重 比如［1，1］＝1 会有两个相同的结果。方法是在pop_back()之后加一句：
7. Permutation
重点也是思路，依次交换： e.g. ABC, 首先看第0位，A先和A交换->ABC; A和B交换->BAC, A和C交换，CBA。 然后看第1位 ABC->ABC和ACB， BAC->BAC和BCA, CBA->CBA和CAB 注意ABC 变成 BAC之后，要变回来ABC,才能变成CBA。 8. Permutation II
思路和上题一样，区别在于 for循环里交换的时候如果num[i]==num[n],i!=n,则跳过这次交换。
9. N-Queen
此题和数独问题类似，每试一个位子，去检查合法性，合法性包括行，列，对角线。 A[i]表示第i行 第A[i]列放置Q。 10. N-Queen II
此题只要求返回解的个数。可以用上题做法，也有更简单的做法，参见http://www.matrix67.com/blog/archives/266
11. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n
此题和permutaion相似，只是k！=n,这里用index<=0和k==0来控制分支。 两次调用foo保证了每个n都可能出现在第i位，1<=i<=k. 而且每个数字后面出现的数字都比前面的数字大，这样避免了重复 另一种方法： 12. Subsets
Given a set of distinct integers, S, return all possible subsets.
此题也是典型的DFS， 是上题k=1,..n的扩展.更直观和简单的一个解题思路是用二进制数字来表示所有的subset. 每一个二进制数字对应一个unique subset, 1表示这个位的数字有，0表示这个位子上的数字无。当然前提先把数组排序（不排序也可以做，排过序答案更整齐） 12.b Subset II
如果有重复怎么做。我们先看没重复的 S=[1,2,3]. 可能的子集是 [], [1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]. 每一次遇到新元素，其实就是加到所有的已有的set里。比如当新元素是2， 那么就要加到[], [1]中，结果是[2],[1,2]。(上题的另一种解法) 如果有重复,那么就不能加入到已有的所有set里，而是只加入上一步生成的set里。比如如果不重复，当遇到新元素3，3要加入到所有已经生成的set中，也就是 [], [1],[2],[1,2]。 但是如果是重复的set S=[1,2,2],当遇到第二个2，就不能加所有的了因为[],[1]已经加过，只需要加上一步生成的,也就是[2],[1,2] 13. Word Search
典型的DFS。 先遍历找第一个字符，找到之后进入DFS搜索模式。注意每匹配一个要做记号，防止loop。返回要把记号去掉。 14. Surrounded Regions
此题先搜索不能被包围的区域，也就是和边界联通的O，先都找出来，标记位D。然后把剩下的O（被包围的）置换成#。 最后把标记位D的位（不能被包围的）还原成O。 15. Word Ladder 这道题是典型的BFS广度优先搜索，这里一并介绍。思路其实比较简单，就是把一个word从头到位依次用a-z替换，然后插入队列末尾。记住用空格来区分不同的层。 16. Palindrome Partitioning 返回所有的partitioning 情况。典型的DFS。 17. Palindrome Partitioning II res[i] 表示s[0..i]的最小cut。res(i) = min [ res(j)+1, j=0..i-1 and s[j:i] 是回文] 0, if s[0,i] 是回文. 我们用一个矩阵mp来记录s[i,j]是不是回文