22. Generate Parentheses
給定 n 對括號，編寫一個函數來生成所有格式正確的括號組合。
範例 1：
輸入：n = 3 輸出：["((()))","(()())","(())()","()(())","()()()"]
Python
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(current: str, open: int, close: int):
if len(current) == 2 * n:
result.append(current)
return
if open < n:
backtrack(current + '(', open + 1, close)
if close < open:
backtrack(current + ')', open, close + 1)
result = []
backtrack("", 0, 0)
return result
16.63MB, 29ms
C++
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
backtrack(result, "", 0, 0, n);
return result;
}
private:
void backtrack(vector<string>& result, string current, int open, int close, int n) {
if (current.length() == 2 * n) {
result.push_back(current);
return;
}
if (open < n) {
backtrack(result, current + '(', open + 1, close, n);
}
if (close < open) {
backtrack(result, current + ')', open, close + 1, n);
}
}
};
15.21MB, 0ms
Javascript
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
const result = [];
const backtrack = (current, open, close) => {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
};
backtrack('', 0, 0);
return result;
};
50.34MB, 61ms
