Command Palette

Search for a command to run...

Hectal
Problem 13.6 · BacktrackingMedium

Generate Parentheses

PatternBacktrackingStack for Matching and Undo

What it teaches: Prune with counts: add '(' while some remain, add ')' only when it would still be balanced.

Practise it on judges as “Generate Parentheses”.

The problem

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

Example 1

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

Example 2

Input: n = 1
Output: [()]

Constraints

  • 1 ≤ n ≤ 8

Pattern clues in the wording

  • → Generate all valid strings
  • → Validity can be checked while building

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 3
["((()))","(()())","(())()","()(())","()()()"]
2
n = 1
["()"]

From slow to fast

Approaches

1. Backtracking with open/close counts · O(4ⁿ / √n) (the Catalan number of results)
1

Backtracking with open/close counts

Time O(4ⁿ / √n) (the Catalan number of results) Space O(n)

If open < n, add '('. If close < open, add ')'. Record when length is 2n. Invalid strings are never built.

Approach 1
import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> out = new ArrayList<>();
        dfs(n, 0, 0, new StringBuilder(), out);
        return out;
    }

    private void dfs(int n, int open, int close, StringBuilder sb, List<String> out) {
        if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
        if (open < n) {
            sb.append('(');
            dfs(n, open + 1, close, sb, out);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            dfs(n, open, close + 1, sb, out);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

Verdict: Generates only valid strings.

Before you submit

Edge cases and common mistakes

Test these inputs

  • n = 1

Mistakes people make

  • Allowing ')' when close == open (produces invalid strings).

Interview

Follow-up questions

How many valid strings are there for n pairs?