Back to solutions

Generate Parentheses

MediumStack & Queue

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Open problem
Constraints
  • 1 <= n <= 8

Backtracking with open/close counts

Time O(4^n / sqrt(n))Space O(n) recursion depth

Build the string character by character. You may add an open bracket while fewer than n are used, and a close bracket while there are unmatched opens. Record strings of length 2n.

#include <bits/stdc++.h>
using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> res;
    string cur;
    function<void(int,int)> bt = [&](int open, int close) {
        if ((int)cur.size() == 2 * n) { res.push_back(cur); return; }
        if (open < n) { cur.push_back('('); bt(open + 1, close); cur.pop_back(); }
        if (close < open) { cur.push_back(')'); bt(open, close + 1); cur.pop_back(); }
    };
    bt(0, 0);
    return res;
}