Link to Question

MEDIUM

Generate Parentheses

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

Example

Input:

n = 3

Output:

["((()))","(()())","(())()","()(())","()()()"]

Explanation:
All valid combinations of 3 pairs of parentheses.

---

Constraints

• 1 ≤ n ≤ 8

---

Solution: Backtracking

• Time Complexity: O(4ⁿ / √n)
• Space Complexity: O(4ⁿ / √n)

C++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string temp;
        vector<string> ans;
        function<void(int, int)> helper = [&](int left, int right) {
            if (left == 0 && right == 0) {
                ans.push_back(temp);
                return;
            }
            if (left) {
                temp += "(";
                helper(left-1, right);
                temp.pop_back();
            }
            if (right > left) {
                temp += ")";
                helper(left, right-1);
                temp.pop_back();
            }
        };
        helper(n, n);
        return ans;
    }
};