22. Generate Parentheses

题目链接：https://leetcode.com/problems/generate-parentheses/description/

题目大意：给出一个数字n，找出所有包含n对()括号对的组合，例子如下：

法一：直接用深搜，将(和)交换着加入string中，然后每得到一个string用stack判断是否是匹配的。代码如下（耗时57ms）：

 1     public List<String> generateParenthesis(int n) {
 2         List<String> s = new ArrayList<String>();
 3         String tmp = "";
 4         dfs(s, tmp, n);
 5         return s;
 6     }
 7     
 8     public static void dfs(List<String> s, String tmp, int n) {
 9         System.out.println(tmp);
10         //递归结束点
11         if(tmp.length() == n * 2) {//验证是否满足括号匹配
12             Stack<Character> stack = new Stack<Character>();
13             boolean flag = true;
14             for(int i = 0; i < n * 2; i++) {
15                 if(tmp.charAt(i) == '(') {
16                     stack.push(tmp.charAt(i));
17                 }
18                 else {
19                     if(stack.isEmpty() || stack.pop() != '(') {
20                         flag = false;
21                         break;
22                     }
23                 }
24             }
25             if(!stack.isEmpty()) {
26                 flag = false;
27             }
28             //如果满足，将string放入list结果集中
29             if(flag == true) {
30                 s.add(tmp);
31             }
32             return;
33         }
34         tmp = tmp + '(';
35         dfs(s, tmp, n);
36         tmp = tmp.substring(0, tmp.length() - 1);//回溯一定要记得将值置回原位，这里采用删除string最后一位置原的办法
37         tmp = tmp + ')';
38         dfs(s, tmp, n);
39     }

View Code

法二（借鉴）：用left和right分别记录左括号和右括号还需要添入的数量，如果left还有剩余加入(，如果right还有剩余且left<right则加入)。当left=right=0时，所得到的字符串一定是满足括号匹配条件的。这个里面有图解：http://blog.csdn.net/u012501459/article/details/46787097。代码如下（耗时3ms）：

 1     public List<String> generateParenthesis(int n) {
 2         List<String> s = new ArrayList<String>();
 3         String tmp = "";
 4         dfs(s, tmp, n, n);
 5         return s;
 6     }
 7     
 8     public static void dfs(List<String> s, String tmp, int left, int right) {
 9         //递归结束条件
10         if(left == 0 && right == 0) {
11             s.add(tmp);
12         }
13         //回溯也会在此发生
14         if(left > 0) {
15             dfs(s, tmp + '(', left - 1, right);
16         }
17         if(right > 0 && left < right) {//别忘了加入left<right条件，这个条件表示当前字符串中已有的(的数量要比)小，才能得到符合括号匹配条件的字符串结果
18             dfs(s, tmp + ')', left, right - 1);
19         }
20     }

View Code

其运行详细结果如下：

n=3时：
(,left=2,right=3--->right>0未执行
((,left=1,right=3--->right>0未执行
(((,left=0,right=3
(((),left=0,right=2
((()),left=0,right=1
((())),left=0,right=0
第一次回溯：
((),left=1,right=2--->回溯到最近的一层执行right>0
(()(,left=0,right=2--->继续正常执行left>0
(()(),left=0,right=1
(()()),left=0,right=0
第二次回溯：
(())
(())(
(())()
第三次回溯：
()
()(
()((
()(()
()(())
第四次回溯：
()()
()()(
()()()
[((())), (()()), (())(), ()(()), ()()()]