# Dfs

## 22. Generate Parentheses 生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Difficulty: Medium 这道题让我们列举出所有的括号字符串,前面还有一题20. Valid Parentheses 验证括号也是关于括号的.这里让列举出所有可能,可以优先考虑递归和DFS.定义left,right分别表示剩余左括号的数量和剩余的右括号的数量.如果在某次的递归中,left>right说明在已经生成的字符串中右括号的数量大于左括号的数量,是不合理的.当left,right都为0的时候,说明已经生成一个可用的括号串.其实这里有DFS的思想.为什么呢.看看下面是怎样递归的顺序,以题目给的例子n=3. ( (( ((( ((() ((()) ((())) (()()) ~ ()()() DFS(深度优先),这里可以想象成左括号优先 解法1 就是上面分析的解法 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; generateParenthesisDFS(n,n,"",res); return res; } void generateParenthesisDFS(int left,int right,string out,vector<string>& res) { if (left>right) return; if (left==0 && right==0) res.

## 17. Letter Combinations of a Phone Number 电话号码的字母组合

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 这道题让我们求电话号码的字母组合, 既2~9中,每个数字都代表2到3个字母,然后给出一个数字的字符串,求出这串数字可能代表的所有字母串.这道题可以用DFS的思想解决,关于DFS可以看二叉树 深度优先搜索（DFS）、广度优先搜索（BFS）,可以简单的了解一下.那为什么说是DFS思想呢,比如给出”2345”,那个对应的结果为adgj,adgk,adgl,adhj,adhk,adhl...cfil这个顺序可以看做DFS的思想.大概这个意思. 解法1 解法1就是上面的分析的解法. class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.