综合文章

# 题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为:

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

给出 n = 2, 生成结果为:

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

# 解题思路

LeetCode里有很多种解题思路: 回溯、动态规划等等.

在这里我主要讲解一种最简单最好理解的方法.

思路:

  1. 输入n, 则就表示会有n个左括号和n个右括号;
  2. 使用递归的方式, 用两个变量l和r分别记录使用了左括号的数量和右括号的数量;
  3. 当l小于n的时候, 则添加上左括号(, 且后面添加的右括号)都不能大于l.

# Coding

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res = [];
    let cycle = (currentStr, l, r) => {
        if (l === n && r === n) { // 当左右括号数量和n相等则返回
            res.push(currentStr);
            return;
        }
        if (l < n) { // 若左括号的数量小于n
            cycle(currentStr + '(', l + 1, r);
        }
        if (l > r) { // 若左括号的数量大于右括号数量
            cycle(currentStr + ')', l, r + 1);
        }
    };
    cycle('', 0, 0);
    return res;
};

执行用时: 60ms, 内存消耗: 35.2MB.

阅读全文

← 整数转罗马数字 →