# 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 的

## &#x32;**. 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.&#x20;

Here b is 2, d is 6 as there are 6 levels.

<https://leetcode.com/articles/generate-parentheses/>

```java
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

```java
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);
        }
    }
}
```