Generate Parentheses

LeetCode 22 | Difficulty: Medium

Medium

Problem Description

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

Example 1:

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

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

- `1 <= n <= 8`

Topics: String, Dynamic Programming, Backtracking

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 308 ms)

Metric	Value
Runtime	308 ms
Memory	N/A
Date	2018-02-21

Solution

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        List<string> result = new List<string>();
    Backtrack(result, new StringBuilder(), 0, 0, n);
    //Backtrack(result, "", 0, 0, n);
    return result;
}

public void Backtrack(IList<string> dp, string temp, int open, int close, int max)
{
    if(open==max && close==max)
    {
        dp.Add(temp);
        return;
    }
    if(open<max)
    {
        Backtrack(dp,temp + "(",open+1,close,max);
        
    }
    if(close<open)
    {
        Backtrack(dp,temp + ")",open,close+1,max);
    }
}

public void Backtrack(IList<string> dp, StringBuilder sb, int open, int close, int max)
{
    if (open == max && close == max)
    {
        dp.Add(sb.ToString());
        return;
    }
    if (open < max)
    {
        sb.Append("(");
        Backtrack(dp, sb, open + 1, close, max);
        sb.Remove(sb.Length-1,1);

    }
    if (close < open)
    {
        sb.Append(")");
        Backtrack(dp, sb, open, close+1, max);
        sb.Remove(sb.Length - 1, 1);
    }
}
}

📜 1 more C# submission(s)

Submission (2018-02-21) — 312 ms, N/A

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        List<string> result = new List<string>();
    //Backtrack(result, new StringBuilder(), 0, 0, n);
    Backtrack(result, "", 0, 0, n);
    return result;
}

public void Backtrack(IList<string> dp, string temp, int open, int close, int max)
{
    if(open==max && close==max)
    {
        dp.Add(temp);
        return;
    }
    if(open<max)
    {
        Backtrack(dp,temp + "(",open+1,close,max);
        
    }
    if(close<open)
    {
        Backtrack(dp,temp + ")",open,close+1,max);
    }
}

public void Backtrack(IList<string> dp, StringBuilder sb, int open, int close, int max)
{
    if (open == max && close == max)
    {
        dp.Add(sb.ToString());
        return;
    }
    if (open < max)
    {
        sb.Append("(");
        Backtrack(dp, sb, open + 1, close, max);
        sb.Remove(sb.Length-1,1);

    }
    if (close < open)
    {
        sb.Append(")");
        Backtrack(dp, sb, open, close+1, max);
        sb.Remove(sb.Length - 1, 1);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Backtracking	$O(n! or 2^n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Identify pruning conditions early to avoid exploring invalid branches.