[leetcode]Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

算法思路：

DFS，对每一位，尝试后缀‘（’ 或 ‘）’，用k记录左括号的个数，用couple记录成功匹配对数，注意剪枝

这个代码是我看到的几乎最简练的算法：[leetcode]Generate Parentheses

代码如下：

 1  public class Solution {
 2      List<String> result = new ArrayList<String>();
 3      public List<String> generateParenthesis(int n) {
 4          dfs(new StringBuilder(),0,0,n);
 5          return result;
 6      }
 7      private void dfs(StringBuilder sb,int k,int couple,int n){
 8          if(k == 0 && couple == n && sb.length() == 2 * n ){
 9              result.add(sb.toString());
10              return;
11          }
12          if( k < 0 || sb.length() > 2 * n) return;//剪枝
13          char[] c = {'(',')'};
14          for(int i = 0; i < 2; i++){
15             k = (i == 0 )? k + 1 : k-1;
16             if(k > 0 && i == 1) {//配对的前提是k>0，即存在未配对的左括号
17                  couple++;
18                  k--;
19              }
20 　　　　     if(k < 0){//如果前面木有左括号，则只能匹配右括号
21                  k++;
22                  continue;
23              }
24              dfs(sb.append(c[i]), k,couple, n);
25              sb.deleteCharAt(sb.length() - 1);
26          }
27      }
28  }

第二遍记录：

同样的DFS，这次的代码可读性可能稍微好一点：

 1 public class Solution {
 2     List<String> res = new ArrayList<String>();
 3     public List<String> generateParenthesis(int n) {
 4         if(n <= 0) return res;
 5         dfs(new StringBuilder(), 0, 0, n);
 6         return res;
 7     }
 8     private void dfs(StringBuilder sb,int l,int k,int n){//k表示左括号个数，l表示当前sb的长度，可省去
 9         if(k == n && l == 2 * n){
10             res.add(sb.toString());
11             return;
12         }
13         if( k > n || 2 * k < l) return;//左括号数> n 或者 右括号比左括号多时，不合法
14         char[] ca = {'(',')'};
15         for(int i = 0; i < 2;i++){
16             sb.append(ca[i]);
17             if(i == 0)
18                 dfs(sb, l + 1, k + 1, n);
19             else
20                 dfs(sb, l + 1, k, n);
21             sb.deleteCharAt(sb.length() - 1);
22         }
23     }
24 }

迷迷糊糊的。。。