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:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题意:  给定一个长度，生成所有此长度的合法括号序列。

 

Solution1：Backtracking.

We can observe that two constraints:

(1)  left Parentheses should come faster ahead to reach given n. 

(2) in each level, we increment left Parentheses count (or right Parentheses count) from given n, and add '(' (or ')') into path

At last, left and right Parentheses count become 0, we can gerenate a result path. 

 

[leetcode]22. Generate Parentheses生成括号 随笔

code:

 1 /*
 2 Time:  O(2^n).
 3 Space: O(n).  use O(n) space to store the sequence(path) 
 4 */
 5 class Solution {
 6     public List<String> generateParenthesis(int n) {
 7         List<String> result = new ArrayList<>();
 8         if (n == 0) return result;
 9         helper("", n, n, result);
10         return result;
11 
12     }
13 
14     private void helper(String path, int left, int right, List<String> result) {
15         // corner
16         if (left > right) return;
17         // base
18         if (left == 0 && right == 0) {
19             result.add(path);
20             return;
21         }
22         if (left > 0) {
23             helper(path + "(", left - 1, right, result);
24         }
25         if (right > 0) {
26             helper(path + ")", left, right - 1, result);
27         }
28     }
29 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄