刷题69——括号生成

108.括号生成

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

重难点

找出括号生成规律

题目分析

1. 括号分成左括号（left）和右括号（right）；
2. 根据n生成n对括号可知：left <=n ,right <= left；
3. 写一个生成括号的函数：记录左括号，右括号的数量，并生成括号存放在res中；
4. 边界：左括号数量不超过n，右括号数量不超过左括号数量，即left < n，right < left
5. 当left == n && right == n时，return res；

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = (n) =>{
    let res = [];
    function dfs(s, left, right){
        if(left == n && right == n) return res.push(s);
        if(left < n) dfs(s+'(', left+1, right);
        if(right < left) dfs(s+')', left, right+1);
    }
    dfs('', 0, 0);
    return res;
}