22. Generate Parentheses

Tags

1. Backtracking
2. String

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

题意：

给定n对括号，写出函数生成所有形成的圆括号的所有组合。

分析：

根据题意及示例的展示，本题首先想到使用递归来做，需要把每种情况都列出来，一步一步构造对应的字符串，通过例子，我们可以把变量提取出来，需要一个str来拼装字符串，一个数组来add，然后题目给定了括号数量n。因此，设定左括号（n）出现次数为指定的n，右括号（m）出现的初始次数为0，当n大于0时，可以放置新的左括号，n-1，m+1。当右括号出现次数大于0时，就可以放置新的右括号。我们可以将string放进参数，这样回溯的时候不必在进行删除处理。

思路：

用两个整数n，m数剩下的左括号"("和右括号")"；

如果n>0，在每个函数调用时添加一个左括号，

而如果m>0，则添加一个右括号；

当m和n为零时将结果追加进入数组并终止递归调用。

复杂度：

时间复杂度O(n²)

Js实现：

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res = [];
    addingpar(res, "", n, 0);
    return res;
};

function addingpar(v,str,n,m) {
    if(n===0 && m===0) {
        v.push(str);
        return;
    }
    if(m > 0){ addingpar(v, str+")", n, m-1); }
    if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
}