> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/cartesian-product/generate-parentheses.md).

# 22. Generate Parentheses

https\://leetcode.com/problems/generate-parentheses/description/

> Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

## Thoughts

DFS:

生成n对所有可能的括号组合。让返回所有组合=>DFS，再配合验证是否合法的+1-1逻辑。

DP:

f\[n]表示给定n时能形成的parentheses，它相当于是从partition拼接而来，也就是不同长度的j和i-j+1两个子结果拼在一起. 比如n = 3时, 相当于对n = 2时加个(), 那么把n = 2时可能组成的所有列出来,包括 n = 1 + 1时 把它们左边的外面加上()即可. f\[0] = ""

f\[1] = (f\[0])

f\[2] = (f\[1]), (f\[0])f\[1]

f\[3] = (f\[0])f\[2], (f\[1])f\[1], (f\[2])

## Code

```cpp
/*
 * @lc app=leetcode id=22 lang=cpp
 *
 * [22] Generate Parentheses
 */

// @lc code=start
class Solution {
public:
    void dfs(int n, string &path, int sum, vector<string> &res) {
        if (n == 0) {
            if (sum == 0) {
                res.push_back(path);
            }
            return;
        } 
        path.push_back('(');
        dfs(n - 1, path, sum + 1, res);
        path.pop_back();
        if (sum > 0) {
            path.push_back(')');
            dfs(n - 1, path, sum - 1, res);
            path.pop_back();
        } 
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string path;
        dfs(n * 2, path, 0, res);
        return res;
    }
};
// @lc code=end


```

```java
class Solution {    
    public List<String> generateParenthesis(int n) {
        List<List<String>> f = new ArrayList<>();
        f.add(Collections.singletonList(""));

        for (int i = 1; i <= n; i++) {
            List<String> list = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                for (String first : f.get(j)) {
                    for (String sec : f.get(i - 1 - j)) {
                        list.add("(" + first + ")" + sec);
                    }
                }
            }

            f.add(list);
        }

        return f.get(f.size() - 1);
    }
}
```

## Analysis

时空复杂度(O(N^2)).