68. Generate Parentheses · DSA Practice

Return all well-formed strings made of n pairs of parentheses, in any order.

Example 1

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input: n = 1

Output: ["()"]

Hint 1

Only add “(” while you have some left, and only add “)” when it closes an open one.

BacktrackingString

Approach 1: Generate all, filter

All 2²ⁿ strings, keep valid ones.

⏱ Time O(2²ⁿ · n)💾 Space O(n)

Approach 2: Constrained backtracking ✅

Never build an invalid prefix.

⏱ Time O(4ⁿ / √n)💾 Space O(n)

Reference solution for Constrained backtracking (time O(4ⁿ / √n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def build(s, opened, closed):
            if len(s) == 2 * n:
                res.append(s)
                return
            if opened < n:
                build(s + '(', opened + 1, closed)     # can always open if any are left
            if closed < opened:
                build(s + ')', opened, closed + 1)     # can close only an open one
        build('', 0, 0)
        return res

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        build(new StringBuilder(), 0, 0, n, res);
        return res;
    }
    private void build(StringBuilder s, int open, int close, int n, List<String> res) {
        if (s.length() == 2 * n) { res.add(s.toString()); return; }
        if (open < n) { s.append('('); build(s, open + 1, close, n, res); s.deleteCharAt(s.length() - 1); }
        if (close < open) { s.append(')'); build(s, open, close + 1, n, res); s.deleteCharAt(s.length() - 1); }
    }
}

class Solution {
    void build(string& s, int open, int close, int n, vector<string>& res) {
        if ((int)s.size() == 2 * n) { res.push_back(s); return; }
        if (open < n) { s.push_back('('); build(s, open + 1, close, n, res); s.pop_back(); }
        if (close < open) { s.push_back(')'); build(s, open, close + 1, n, res); s.pop_back(); }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string s;
        build(s, 0, 0, n, res);
        return res;
    }
};

function generateParenthesis(n) {
  const res = [];
  const build = (s, open, close) => {
    if (s.length === 2 * n) { res.push(s); return; }
    if (open < n) build(s + '(', open + 1, close);
    if (close < open) build(s + ')', open, close + 1);
  };
  build('', 0, 0);
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Recursion & Backtracking.