22. Generate Parentheses

Posted on

Description

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

Example

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

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

最直接是递归然后剪枝，因为需要成对判断合法性，所以如果left > right的时候就可以剪掉了。
同时如果left == 0 的时候都可以直接把right的括号补全了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    if (n===0) return [];
    if (n===1) return ['()'];
    
    var result = [];
    search(n,n,'',result);
    return result;
};

function search(left,right,cur,result){
    if (left < 0 || right < 0 || left > right)return;
    if (left == 0){
        for (let i = right; i > 0; i--){
            cur += ')';
        }   
        result.push(cur);
        return;
    }
    
    search(left - 1, right, cur + '(', result);
    search(left, right - 1, cur + ')', result);
}