22.GenerateParentheses.md

题目地址

https://leetcode-cn.com/problems/generate-parentheses

题目描述

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

示例：

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

思路

深度优先搜索(回溯思想)，从空字符串开始构造，做加法。

关键点

• 当 l < r 时记得剪枝

代码

• 语言支持：JS

/**
 * @param {number} n
 * @return {string[]}
 * @param l 左括号已经用了几个
 * @param r 右括号已经用了几个
 * @param str 当前递归得到的拼接字符串结果
 * @param res 结果集
 */
const generateParenthesis = function (n) {
    const res = [];

    function dfs(l, r, str) {
        if (l == n && r == n) {
            return res.push(str);
        }
        // l 小于 r 时不满足条件 剪枝
        if (l < r) {
            return;
        }
        // l 小于 n 时可以插入左括号，最多可以插入 n 个
        if (l < n) {
            dfs(l + 1, r, str + '(');
        }
        // r < l 时 可以插入右括号
        if (r < l) {
            dfs(l, r + 1, str + ')');
        }
    }
    dfs(0, 0, '');
    return res;
};

复杂度分析

• 时间复杂度：O(2^N)
• 空间复杂度：O(2^N)