Generate Parentheses: track open and close counts | Coding Problems: DSA

Q: What is the Generate Parentheses problem?

Given n pairs of parentheses, generate every string of n opens and n closes that is wellformed, meaning every closer has a matching earlier opener. For n = 3, there are 5 valid strings. The brute force would generate all 2^6 = 64 strings and filter, but the elegant approach never builds an invalid s

Q: Why does the close < open rule keep strings valid?

The invariant close < open means at every point in the string, the number of closes never exceeds the number of opens. This guarantees every prefix has at least as many opens as closes, which is exactly the definition of a valid prefix. Since every prefix is valid and the string ends with equal coun

Q: How does the backtracking work?

At each step, you have at most two choices: place an open or place a close. You try each valid choice by appending the character, recursing with updated counts, and then deleting the character to undo. The base case records the string when it reaches length 2n. package com.bank.core; public class Ba

Q: What is the Catalan number connection?

The number of valid parentheses strings for n pairs is the nth Catalan number, which is C(2n,n)/(n+1). For n=3 it is 5, for n=4 it is 14. This grows much slower than 2^(2n), which shows why the constrained approach is far more efficient than generating all binary strings and filtering. package com.b

Q: What are the edge cases?

For n=0 there is one valid string: the empty string. For n=1 there is exactly one: "()". For large n the Catalan number grows rapidly, so n must stay modest to avoid memory issues. package com.bank.service; public class GenerateEdgeCases { public static void main(String[] args) { System.out.println(

Q: What are common mistakes?

The most common mistake is generating all 2^(2n) strings and filtering, which is exponentially wasteful. Another is using string concatenation instead of StringBuilder, which creates a new string on every append and makes the algorithm much slower. A third is forgetting the delete step after recursi

Q: How is this applied in banking?

At the National Bank of India, the approvalrule builder enumerates every valid nesting pattern for nested approval workflows. For a given number of subapproval levels, the tool generates all wellformed bracket structures so the governance team can review every possible workflow template. Constrained

Q: What should a senior engineer know?

The constrained backtracking technique, enforcing validity during construction rather than filtering afterward, is a general optimization pattern. It applies to generating valid expressions, balanced tag structures, Sudoku solvers, and NQueens. Recognizing that the count is a Catalan number signals

Definition

Open while open < n, close while close < open, record at length 2n; never generate an invalid string.

Generate Parentheses – produce every well-formed string of n open and n close parentheses using constrained backtracking.
Two rules – append ( while open < n; append ) only while close < open.
Invariant – close < open guarantees every prefix stays valid, so no validity check is needed at the end.
Count – the number of results is the nth Catalan number.
Backtracking – append one character, recurse, then delete the last character to undo.
Efficiency – only valid strings are ever built, avoiding the exponential waste of generate-then-filter.

At the National Bank of India, an approval-rule builder lets designers compose nested approval brackets, where an opener starts a sub-approval and a closer finishes it. For n levels, the tool enumerates every valid nesting pattern. A designer writes the pattern left to right: she can start a new sub-approval as long as she has starts remaining, and she can finish one only if there is an unfinished one open. Every pattern she writes is valid by construction.

Understanding the Concepts

What is the Generate Parentheses problem?

Given n pairs of parentheses, generate every string of n opens and n closes that is well-formed, meaning every closer has a matching earlier opener. For n = 3, there are 5 valid strings. The brute force would generate all 2^6 = 64 strings and filter, but the elegant approach never builds an invalid string.

JAVA

package com.bank.service;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public static List<String> generate(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

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

    public static void main(String[] args) {
        System.out.println(generate(3));
    }
}

TEXT

[((())), (()()), (())(), ()(()), ()()()]

Why does the close < open rule keep strings valid?

The invariant close < open means at every point in the string, the number of closes never exceeds the number of opens. This guarantees every prefix has at least as many opens as closes, which is exactly the definition of a valid prefix. Since every prefix is valid and the string ends with equal counts, the complete string is balanced.

JAVA

package com.bank.core;

public class InvariantExplanation {
    public static void main(String[] args) {
        // Building "(())" step by step:
        // After '(':  open=1, close=0  (close < open: can close)
        // After '((':  open=2, close=0
        // After '(()': open=2, close=1 (close < open: can still close)
        // After '(())': open=2, close=2 (done, length = 2n)
        System.out.println("At every step: close <= open");
        System.out.println("This means every prefix has at least as many '(' as ')'");
        System.out.println("A prefix with more ')' than '(' would be invalid");
        System.out.println("The rule prevents this from ever happening");
    }
}

TEXT

At every step: close <= open
This means every prefix has at least as many '(' as ')'
A prefix with more ')' than '(' would be invalid
The rule prevents this from ever happening

How does the backtracking work?

At each step, you have at most two choices: place an open or place a close. You try each valid choice by appending the character, recursing with updated counts, and then deleting the character to undo. The base case records the string when it reaches length 2n.

JAVA

package com.bank.core;

public class BacktrackingTrace {
    static int callCount = 0;

    static void trace(StringBuilder sb, int open, int close, int n) {
        callCount++;
        if (sb.length() == 2 * n) {
            System.out.println("  Result: " + sb);
            return;
        }
        if (open < n) {
            sb.append('(');
            trace(sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            trace(sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        trace(new StringBuilder(), 0, 0, 2);
        System.out.println("Total recursive calls: " + callCount);
    }
}

TEXT

  Result: (())
  Result: ()()
Total recursive calls: 7

What is the Catalan number connection?

The number of valid parentheses strings for n pairs is the nth Catalan number, which is C(2n,n)/(n+1). For n=3 it is 5, for n=4 it is 14. This grows much slower than 2^(2n), which shows why the constrained approach is far more efficient than generating all binary strings and filtering.

JAVA

package com.bank.core;

public class CatalanNumbers {
    public static void main(String[] args) {
        System.out.println("n=1: 1 valid string, 2^2=4 total");
        System.out.println("n=2: 2 valid strings, 2^4=16 total");
        System.out.println("n=3: 5 valid strings, 2^6=64 total");
        System.out.println("n=4: 14 valid strings, 2^8=256 total");
        System.out.println("n=10: 16796 valid strings, 2^20=1048576 total");
        System.out.println("Catalan numbers also count binary trees and triangulations");
    }
}

TEXT

n=1: 1 valid string, 2^2=4 total
n=2: 2 valid strings, 2^4=16 total
n=3: 5 valid strings, 2^6=64 total
n=4: 14 valid strings, 2^8=256 total
n=10: 16796 valid strings, 2^20=1048576 total
Catalan numbers also count binary trees and triangulations

What are the edge cases?

For n=0 there is one valid string: the empty string. For n=1 there is exactly one: "()". For large n the Catalan number grows rapidly, so n must stay modest to avoid memory issues.

JAVA

package com.bank.service;

public class GenerateEdgeCases {
    public static void main(String[] args) {
        System.out.println("n=0: " + GenerateParentheses.generate(0)); // [""]
        System.out.println("n=1: " + GenerateParentheses.generate(1)); // ["()"]
        System.out.println("n=2: " + GenerateParentheses.generate(2)); // ["(())", "()()"]
    }
}

TEXT

n=0: []
n=1: [()]
n=2: [(()), ()()]

What are common mistakes?

The most common mistake is generating all 2^(2n) strings and filtering, which is exponentially wasteful. Another is using string concatenation instead of StringBuilder, which creates a new string on every append and makes the algorithm much slower. A third is forgetting the delete step after recursion, which corrupts the builder for subsequent branches.

JAVA

package com.bank.core;

public class GenerateMistakes {
    public static void main(String[] args) {
        // Mistake 1: generate all and filter
        System.out.println("Wrong: generate 2^(2n) strings, filter valid -> exponential waste");
        System.out.println("Right: constrained backtracking, only valid strings built");

        // Mistake 2: string concatenation
        System.out.println("Wrong: s + '(' creates new String each time");
        System.out.println("Right: StringBuilder with append and deleteCharAt");

        // Mistake 3: forgetting to undo
        System.out.println("Wrong: no deleteCharAt after recursion -> corrupted builder");
    }
}

TEXT

Wrong: generate 2^(2n) strings, filter valid -> exponential waste
Right: constrained backtracking, only valid strings built
Wrong: s + '(' creates new String each time
Right: StringBuilder with append and deleteCharAt
Wrong: no deleteCharAt after recursion -> corrupted builder

How is this applied in banking?

At the National Bank of India, the approval-rule builder enumerates every valid nesting pattern for nested approval workflows. For a given number of sub-approval levels, the tool generates all well-formed bracket structures so the governance team can review every possible workflow template. Constrained generation ensures every template is valid by construction.

JAVA

package com.bank.service;

import java.util.List;

public class ApprovalTemplateGenerator {
    public static void main(String[] args) {
        int levels = 3;
        List<String> templates = GenerateParentheses.generate(levels);
        System.out.println("Valid approval templates for " + levels + " levels:");
        for (String t : templates) {
            System.out.println("  " + t);
        }
    }
}

TEXT

Valid approval templates for 3 levels:
  ((()))
  (()())
  (())()
  ()(())
  ()()()

What should a senior engineer know?

The constrained backtracking technique, enforcing validity during construction rather than filtering afterward, is a general optimization pattern. It applies to generating valid expressions, balanced tag structures, Sudoku solvers, and N-Queens. Recognizing that the count is a Catalan number signals mathematical maturity. The same problem can also be solved iteratively using a queue-based BFS approach, though the recursive version is cleaner.

JAVA

package com.bank.core;

public class SeniorGenerateNotes {
    public static void main(String[] args) {
        System.out.println("Pattern: constrained backtracking (validity as pruning)");
        System.out.println("Also applies to: Sudoku, N-Queens, valid expressions");
        System.out.println("Count = Catalan number = C(2n,n)/(n+1)");
        System.out.println("Alternative: BFS with queue of (string, open, close) states");
    }
}

TEXT

Pattern: constrained backtracking (validity as pruning)
Also applies to: Sudoku, N-Queens, valid expressions
Count = Catalan number = C(2n,n)/(n+1)
Alternative: BFS with queue of (string, open, close) states

Visual Overview

DIAGRAM

  Backtracking Tree for n=2
  ──────────────────────────

                    ""
                   / 
                  (
                /   \
              ((     ()
              |      |
             (()    ()(
              |      |
             (())   ()()

  Results: "(())", "()()"
  Only valid branches explored

DIAGRAM

  Decision at each node
  ──────────────────────
  Can I place '(' ?  →  open < n
  Can I place ')' ?  →  close < open
  Am I done?         →  length == 2n

  Both conditions can be true → two branches
  Only one true → one branch
  Neither true → impossible (never happens)

Key Takeaway

Generate Parentheses is a backtracking problem where the elegance comes from never building an invalid string. I track two counters, how many opens and how many closes I have placed, and I build the string one character at a time. I may append an open parenthesis while the open count is below n, and I may append a close only when the close count is strictly less than the open count. When the string reaches length 2n, it is guaranteed balanced.

The close < open invariant is the key. It ensures that at every point in the string, the number of closes never exceeds the number of opens, which means every prefix stays valid. Because invalid prefixes are never built, every leaf of the recursion is a valid string, and the total count is the nth Catalan number, which is dramatically fewer than the 2^(2n) candidates a brute-force approach would generate.

I use StringBuilder with append-recurse-deleteCharAt for efficient backtracking. String concatenation would allocate a new object on every recursive call, which is much slower. The delete step after recursion restores the builder for the next branch, and forgetting it is a classic bug that corrupts subsequent results.

In my project at the National Bank of India, this constrained backtracking generated all valid nesting templates for an approval-rule builder, so the governance team could review every possible workflow shape. Enforcing the two placement rules during construction guaranteed every template was valid by construction.

Remember one sentence: place an open while opens remain, place a close only while closes trail opens, and the result is every valid combination with no wasted generation.

---