22. Generate Parentheses
https://leetcode.com/problems/generate-parentheses/
brute force
gen all the permutation of parentheses, then validate them one by one
O(2^2n*n), 最後乘上 n 是 validate 的
2. dfs+backtracking
from "" to dfs gen string
依然可以畫出樹狀圖, 樹狀圖很重要
use adding
但這題是可以在中間就判斷是否合法 n=3, 只有三個左括號三個右括號
這題只要達到如此條件就可以合法(爾且因為這題只有()) 左隨時可以加 別超標(n=3) 右不能先出現, 左個數>右個數
n > left > right, so n > right 所以不用寫
time complexity:
This assumes you are doing constant amount of work in each call. In general, if you are doing k amount of work(outside calling functions recursively), then time complexity will be O(b^d * k)., O(2^d*k)
Taking the above example, n= 3 pairs. 2^0+2^1+2^2+..........+2^6.
Here b is 2, d is 6 as there are 6 levels.
https://leetcode.com/articles/generate-parentheses/
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
gen(0, 0, "", result, n);
return result;
}
private void gen(int left, int right, String s, List<String> result, int n) {
//termiator
if (left == n && right == n) {
result.add(s);
}
// drill down
if (left < n) {
gen(left + 1, right, s + "(", result, n);
}
if (left > right) {
gen(left, right + 1, s + ")", result, n);
}
}
}
another way, use subtract
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
gen(n, n, "", result);
return result;
}
private void gen(int left, int right, String s, List<String> result) {
//termiator
if (left == 0 && right == 0) {
result.add(s);
return;
}
// drill down
if (left > 0) {
gen(left - 1, right, s + "(", result);
}
if (right > left) {
gen(left, right - 1, s + ")", result);
}
}
}
Last updated
Was this helpful?