Generate Parentheses

Generate Parentheses

給定一個數字n，生成符合要求的n對括号

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:

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

1 package com.rust.TestString;
 2 
 3 import java.util.ArrayList;
 4 import java.util.List;
 5 
 6 class solution {
 7     List<String> res = new ArrayList<String>();
 8     public List<String> generateParenthesis(int n) {
 9         if (n == 0) {
10             res.add("");
11             return res;
12         }
13         addBrackets("", 0, 0, n);//這個遞歸并沒有傳回的條件，跑到完為止
14         return res;
15     }
16     public void addBrackets(String str,int leftB,int rightB,int n) {
17         if (leftB == n && rightB == n) {
18             res.add(str);
19         }// 每次遞歸進來，根據現有情況，還會分割成不同的情況
20         if (leftB < n) {
21             addBrackets(str + "(", leftB + 1, rightB, n);
22         } 
23         if (rightB < leftB) {
24             addBrackets(str + ")", leftB, rightB + 1, n);
25         }
26     }
27 }
28 public class GenerateParentheses {
29     public static void main(String args[]){
30         solution output = new solution();
31         List<String> out = output.generateParenthesis(3);
32         System.out.println(out.size());
33         for (int i = 0; i < out.size(); i++) {
34             System.out.println(out.get(i));
35         }
36     }
37 }