Backtracking
Time = O(2^n)
Space = O(n)
Java 用 StringBuilder:
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
parenthesisHelper(0, 0, n, sb, res);
return res;
}
private void parenthesisHelper(int left, int right, int n, StringBuilder sb, List<String> res) {
if (left == n && right == n) {
res.add(sb.toString());
return;
}
if (left < n) {
parenthesisHelper(left + 1, right, n, sb.append("("), res);
sb.deleteCharAt(sb.length() - 1);
}
if (right < left) {
parenthesisHelper(left, right + 1, n, sb.append(")"), res);
sb.deleteCharAt(sb.length() - 1);
}
}
}
Java 用 String:
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
parenthesisHelper(0, 0, n, "", res);
return res;
}
private void parenthesisHelper(int left, int right, int n, String s, List<String> res) {
if (left == n && right == n) {
res.add(s);
return;
}
if (left < n) {
parenthesisHelper(left + 1, right, n, s + "(", res);
}
if (right < left) {
parenthesisHelper(left, right + 1, n, s + ")", res);
}
}
}
Python:
class Solution:
def generateParenthesis(self, n: 'int') -> 'List[str]':
res = []
self.helper(0, 0, n, "", res)
return res
def helper(self, left, right, n, cur, res):
if left == n and right == n:
res.append(cur)
return
if left < n:
self.helper(left + 1, right, n, cur + "(", res)
if right < n and left > right:
self.helper(left, right + 1, n, cur + ")", res)