LeetCode-22-括号生成

字符串 回溯算法

原题地址：括号生成

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

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

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

构造法

当$n=1$时，结果只有一种，为()。而当$n>1$时，先构造$n-1$的解，然后在它的基础上每个位置加上一对括号，再去重即为$n$的解。代码如下：

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis1 = function(n) {
    if (n === 0) {
        return [];
    }
    if (n === 1) {
        return ['()']
    }
    let set = new Set(); // 利用set去重
    let result = generateParenthesis1(n - 1); // 先递归生成n-1的解
    for (let item of result) {
        for (let i = 0; i < item.length; i ++) {
            // 每个位置加上一对括号
            set.add(`${item.slice(0, i)}()${item.slice(i)}`);
        }
    }
    return [...set];
};

测试：

let start = new Date();
const test = generateParenthesis1;
console.log(test(3)); // [ '()()()', '(())()', '()(())', '(()())', '((()))' ]
console.log(new Date().getTime() - start.getTime()); // 3

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 29,2019