給定正整數(shù)，返回這個(gè)正整數(shù)組成的有效括號(hào)組成的數(shù)組庆冕。
使用回溯法参淫，left和right表示剩余的括號(hào)數(shù)目，所以left > right 的時(shí)候需要退出愧杯。
- 時(shí)間復(fù)雜度
- 空間復(fù)雜度
- Runtime: 80 ms, faster than 74.26%
- Memory Usage: 39.1 MB, less than 56.85%
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
var res = []
generateParenthesisDFS(res, n, n, '')
return res
};
var generateParenthesisDFS = function(res, left, right, cur){
if(left > right) return
if(left === 0 && right ===0){
res.push(cur)
}
if(left > 0) generateParenthesisDFS(res, left - 1, right, cur + '(')
if(right > 0) generateParenthesisDFS(res, left, right - 1, cur + ')')
}
另解：
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
var res = []
backTrack(res, '', 0, 0, n)
return res
};
var backTrack = function(res, cur, left, right, n){
if(cur.length === 2*n){
if(res.indexOf(cur) === -1) res.push(cur)
return
}
if(left < n){
backTrack(res, cur+'(', left + 1, right, n)
}
if(left > right){
backTrack(res, cur+')', left, right + 1, n)
}
}
