22. Generate Parentheses

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {string[]}
 */

题目给了一个数字 n，要求我们求出 n 对括号的所有合法的排列组合

解题思路

这题需要用递归的思路来做，递归函数接收三个参数：

• 左括号数量
• 右括号数量
• 当前的组合字符串

递归的终止条件是：左右括号数量相同且等于 n

在递归中，如果左括号数量小于 n，我们可以插入一个左括号；如果右括号数量小于左括号，我们可以插入一个右括号

Javascript

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res = []

    const dfs = (leftP, rightP, str) => {
        if(leftP === rightP && leftP === n) {
            res.push(str)
            return
        }
        if(leftP < n) {
            dfs(leftP + 1, rightP, str + '(')
        }
        if(rightP < leftP) {
            dfs(leftP, rightP + 1, str + ')')
        }
    }
    dfs(0, 0, '')

    return res
};