Definition
- Generate Parentheses – produce all well-formed strings of n open and n close parentheses using constrained backtracking.
- Placement rules – append
(whileopen < n; append)only whileclose < open. - Invariant –
close < openkeeps every prefix valid, so no post-generation filtering is needed. - Count – results equal the nth Catalan number, which is C(2n,n)/(n+1).
- Backtracking – append, recurse, undo (delete last character) at each step.
- Efficiency – only valid strings are built, avoiding exponential waste.
The National Bank of India generates all valid nesting patterns for approval workflows. An opener starts a sub-approval and a closer finishes the most recent one. A clerk writes the pattern left to right. She may start a new sub-approval as long as she has not used all her starts, and she may finish one only if there is an unfinished one open. Every pattern she writes is automatically valid.
Understanding the Concepts
What is the problem?
Given n pairs of parentheses, generate every string of n opens and n closes that is well-formed. For n = 3 there are exactly 5 valid strings. The brute force generates all 2^(2n) binary strings and filters, but the elegant approach never builds an invalid string.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class GenerateParenthesesBacktrack {
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("n=3: " + generate(3));
}
}
n=3: [((())), (()()), (())(), ()(()), ()()()]
Why do the two placement rules guarantee validity?
The rule open < n means you can only place an open if you still have budget. The rule close < open means you can only place a close if there is an unmatched open before it. Together, they ensure every prefix has at least as many opens as closes, which is the definition of a valid prefix. Since the string ends with equal counts, it is balanced.
package com.bank.core;
public class RuleExplanation {
public static void main(String[] args) {
System.out.println("Rule 1: open < n -> budget for opens remains");
System.out.println("Rule 2: close < open -> unmatched open exists");
System.out.println("Together: every prefix has opens >= closes");
System.out.println("At end: opens == closes == n -> balanced");
}
}
Rule 1: open < n -> budget for opens remains
Rule 2: close < open -> unmatched open exists
Together: every prefix has opens >= closes
At end: opens == closes == n -> balanced
How does the backtracking tree look?
At each node, you have at most two branches: place open or place close. The constraints prune invalid branches early. For n=2, only 7 recursive calls produce 2 results, compared to 16 candidates in brute force.
package com.bank.core;
public class BacktrackTree {
static int calls = 0;
static void count(int open, int close, int n, int len) {
calls++;
if (len == 2 * n) return;
if (open < n) count(open + 1, close, n, len + 1);
if (close < open) count(open, close + 1, n, len + 1);
}
public static void main(String[] args) {
count(0, 0, 3, 0);
System.out.println("Recursive calls for n=3: " + calls);
System.out.println("Brute force candidates: " + (int) Math.pow(2, 6));
}
}
Recursive calls for n=3: 21
Brute force candidates: 64
What is the Catalan number connection?
The count of valid strings is the nth Catalan number. For n=3 it is 5, for n=4 it is 14, for n=10 it is 16796. This is much smaller than 2^(2n), showing the efficiency of constrained generation. Catalan numbers also count binary trees and polygon triangulations.
package com.bank.core;
public class CatalanCount {
public static void main(String[] args) {
System.out.println("n=3: Catalan=5, 2^6=64");
System.out.println("n=5: Catalan=42, 2^10=1024");
System.out.println("n=10: Catalan=16796, 2^20=1048576");
}
}
n=3: Catalan=5, 2^6=64
n=5: Catalan=42, 2^10=1024
n=10: Catalan=16796, 2^20=1048576
What are common mistakes?
Generating all strings and filtering is the classic naive mistake. Using string concatenation instead of StringBuilder creates excessive garbage. Forgetting the delete step after recursion corrupts subsequent branches.
package com.bank.core;
public class BacktrackMistakes {
public static void main(String[] args) {
System.out.println("Mistake 1: generate all 2^(2n) and filter -> exponential waste");
System.out.println("Mistake 2: s + '(' instead of StringBuilder -> GC pressure");
System.out.println("Mistake 3: forget deleteCharAt -> corrupted builder");
}
}
Mistake 1: generate all 2^(2n) and filter -> exponential waste
Mistake 2: s + '(' instead of StringBuilder -> GC pressure
Mistake 3: forget deleteCharAt -> corrupted builder
What are the edge cases?
For n=0 the result is an empty list or a list with one empty string depending on interpretation. For n=1 there is exactly one result: "()". Large n produces many results due to Catalan growth.
package com.bank.service;
public class BacktrackEdgeCases {
public static void main(String[] args) {
System.out.println("n=0: " + GenerateParenthesesBacktrack.generate(0));
System.out.println("n=1: " + GenerateParenthesesBacktrack.generate(1));
System.out.println("n=4 count: " + GenerateParenthesesBacktrack.generate(4).size());
}
}
n=0: []
n=1: [()]
n=4 count: 14
How is this applied in banking?
At the National Bank of India, the approval-rule builder enumerates all valid workflow nesting structures for n levels. Governance reviews every template shape. Constrained generation guarantees each template is valid by construction, saving the review team from examining nonsensical patterns.
package com.bank.service;
import java.util.List;
public class WorkflowTemplates {
public static void main(String[] args) {
int levels = 3;
List<String> templates = GenerateParenthesesBacktrack.generate(levels);
System.out.println("Valid workflows for " + levels + " levels:");
for (String t : templates) {
System.out.println(" " + t);
}
}
}
Valid workflows for 3 levels:
((()))
(()())
(())()
()(())
()()()
What should a senior engineer know?
This constrained backtracking technique, enforcing validity as pruning, generalizes to Sudoku, N-Queens, and valid expression generation. The BFS alternative uses a queue of (string, open, close) states. The mathematical connection to Catalan numbers signals maturity. Time complexity is O(4^n / sqrt(n)) which is the Catalan bound.
package com.bank.core;
public class SeniorBacktrackNotes {
public static void main(String[] args) {
System.out.println("Pattern: validity constraints as pruning");
System.out.println("Generalizes to: Sudoku, N-Queens, expressions");
System.out.println("Alternative: BFS queue of (string, open, close)");
System.out.println("Time: O(4^n / sqrt(n)) = Catalan bound");
}
}
Pattern: validity constraints as pruning
Generalizes to: Sudoku, N-Queens, expressions
Alternative: BFS queue of (string, open, close)
Time: O(4^n / sqrt(n)) = Catalan bound
Visual Overview
Backtracking Tree for n=2
──────────────────────────
""
/
(
/ \
(( ()
| |
(() ()(
| |
(()) ()()
Both leaves are valid strings.
No invalid prefix was ever built.
Constraint Check at Each Node
──────────────────────────────
open < n ? → can place '('
close < open ? → can place ')'
length == 2n ? → record result
Key Takeaway
This problem generates all well-formed strings of n open and n close parentheses using constrained backtracking. I build the string one character at a time with two counters. I may place an open while the open count is below n, and a close only while the close count is strictly less than the open count. When the string reaches length 2n, it is guaranteed balanced and I record it.
The close < open invariant is what prevents invalid prefixes. Because no invalid string is ever started, every leaf of the recursion tree is a valid result, and the total count is the nth Catalan number, which grows far slower than the 2^(2n) brute-force candidates. Using StringBuilder with append-recurse-deleteCharAt keeps the backtracking efficient without string allocation overhead.
This constrained backtracking technique, enforcing validity during construction rather than filtering afterward, is a general optimization pattern. It applies equally to Sudoku, N-Queens, and valid expression generation. Recognizing the Catalan number connection signals mathematical maturity to an interviewer.
In my project at the National Bank of India, the approval-rule builder used this to enumerate every valid nesting template for nested approval workflows. Each template was valid by construction, so the governance team reviewed only well-formed structures without wading through nonsensical patterns.
Remember one sentence: place an open while budget remains, place a close only while closes trail opens, and every string built is valid without any filtering.
---