0022._Generate_Parentheses

发表于 分类于 ， ，

022. generate-parentheses

难度: Medium

刷题内容

原题连接

内容描述

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
2
3
4
5
6
7
8

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题方案

**- 时间复杂度: O(2N)**- 空间复杂度: O(N)**

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 递归函数
 * @param left  剩余的左括号
 * @param right 剩余的又括号
 * @param str  当前已拼装括号的字符串
 * @param list  最终结果集
 */
let helper = function (left,right,str,list) {
    //当前右括号大于左括号
    if (left > right){
        return ;
    }
    //左括号，右括号均无剩余，作为终值填充
    if(left === 0 && right === 0){
        list.push(str);
        return ;
    }
    //左括号有剩余
    if(left > 0){
        helper(left - 1,right,str + '(',list);
    }
    //右括号有剩余
    if(right > 0){
        helper(left,right - 1,str + ')',list);
    }
};
/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
    let list = [];
    helper(n,n,'',list);
    return list;
};