LeetCode 22. Generate Parentheses

Recursion

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Solution:

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
    
    void dfs(string s, int open, int close, vector<string>& parentheses) {
        if (close < open) {
            return;
        }
        
        if (open == 0) {
            string temp(close, ')');
            s += temp;
            parentheses.push_back(s);
        } else {
            dfs(s + "(", open - 1, close, parentheses);
            dfs(s + ")", open, close - 1, parentheses);
        }
    }
    
public:
    vector<string> generateParenthesis(int n) {
        vector<string> parentheses;
        dfs("", n, n, parentheses);
        return parentheses;
    }
};