Generate Parentheses

Problem

Given an integer n, return all combinations of n well-formed pairs of parentheses, in any order.

Constraints

• 1 ≤ n ≤ 8

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def generateParenthesis(self, n):
        res = []
        def bt(cur, op, cl):
            if len(cur) == 2 * n:
                res.append(cur); return
            if op < n:
                bt(cur + '(', op + 1, cl)
            if cl < op:
                bt(cur + ')', op, cl + 1)
        bt('', 0, 0)
        return res

Java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String current,
                           int open, int close, int n) {
        // Base case
        if (current.length() == n * 2) {
            result.add(current);
            return;
        }

        // Add opening parenthesis
        if (open < n) {
            backtrack(result, current + "(", open + 1, close, n);
        }

        // Add closing parenthesis
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, n);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.