0022._Generate_Parentheses.md

022. generate-parentheses

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/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:

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

解题方案

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

代码：

/**
 * 递归函数
 * @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;
};