Definition
- Balanced Parentheses – generate all valid strings of N open and N close parentheses using constrained backtracking.
- Two placement rules – append
(whileopenCount < N; append)only whilecloseCount < openCount. - Invariant –
closeCount < openCountensures every prefix has at least as many opens as closes. - Count – the number of valid results is the Nth Catalan number.
- Backtracking – append one character, recurse with updated counts, then delete the character to undo.
- No filtering – every string built is valid by construction.
At the National Bank of India, nested approval brackets must open and close in balance. For N levels, the governance team wants every valid bracketing. A designer writes the pattern left to right: she can open a new bracket as long as she has brackets left, and she can close one only if there is an unclosed bracket waiting. Every pattern she writes is automatically valid.
Understanding the Concepts
What is the problem?
Generate all strings of N open and N close parentheses that are well-formed. For N=3 there are 5 valid strings. The brute force generates all 2^(2N) binary strings and filters, but the elegant approach builds only valid strings.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class BalancedParentheses {
public static List<String> generate(int n) {
List<String> result = new ArrayList<>();
build(result, new StringBuilder(), 0, 0, n);
return result;
}
private static void build(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('(');
build(result, sb, open + 1, close, n);
sb.deleteCharAt(sb.length() - 1);
}
if (close < open) {
sb.append(')');
build(result, sb, open, close + 1, n);
sb.deleteCharAt(sb.length() - 1);
}
}
public static void main(String[] args) {
System.out.println("N=3: " + generate(3));
System.out.println("Count: " + generate(3).size());
}
}
N=3: [((())), (()()), (())(), ()(()), ()()()]
Count: 5
Why do the two rules guarantee validity?
open < n means you still have open-bracket budget. close < open means there is at least one unmatched open waiting. Together they ensure every prefix has at least as many opens as closes, which is the definition of a valid prefix. When length reaches 2N with equal counts, the string is balanced.
package com.bank.core;
public class ValidityProof {
public static void main(String[] args) {
// Building "(())" step by step:
System.out.println("After '(': open=1 close=0 -> valid prefix");
System.out.println("After '((': open=2 close=0 -> valid prefix");
System.out.println("After '(()': open=2 close=1 -> valid prefix");
System.out.println("After '(())': open=2 close=2 -> balanced!");
System.out.println("At every step: opens >= closes (invariant holds)");
}
}
After '(': open=1 close=0 -> valid prefix
After '((': open=2 close=0 -> valid prefix
After '(()': open=2 close=1 -> valid prefix
After '(())': open=2 close=2 -> balanced!
At every step: opens >= closes (invariant holds)
How does the backtracking tree look?
Each node has at most two branches: place open or place close. Invalid branches are pruned by the two rules. For N=2, only 7 calls produce 2 valid strings.
package com.bank.core;
public class BacktrackTreeSize {
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("N=3 recursive calls: " + calls);
System.out.println("Brute force: 2^6 = " + (int)Math.pow(2, 6));
}
}
N=3 recursive calls: 21
Brute force: 2^6 = 64
What is the Catalan number connection?
The count of valid strings is the Nth Catalan number = C(2N,N)/(N+1). For N=3: 5, N=5: 42, N=10: 16796. Catalan numbers also count binary tree shapes and polygon triangulations.
package com.bank.core;
public class CatalanFacts {
public static void main(String[] args) {
System.out.println("N=3: Catalan=5, brute=64");
System.out.println("N=5: Catalan=42, brute=1024");
System.out.println("N=10: Catalan=16796, brute=1048576");
System.out.println("Also counts: binary trees, triangulations");
}
}
N=3: Catalan=5, brute=64
N=5: Catalan=42, brute=1024
N=10: Catalan=16796, brute=1048576
Also counts: binary trees, triangulations
What are the edge cases?
N=0 produces an empty list. N=1 produces one string: "()". Large N is bounded by Catalan growth, which is approximately 4^N / (N^1.5 * sqrt(pi)), so results grow fast.
package com.bank.service;
public class BalancedEdgeCases {
public static void main(String[] args) {
System.out.println("N=0: " + BalancedParentheses.generate(0));
System.out.println("N=1: " + BalancedParentheses.generate(1));
System.out.println("N=4 count: " + BalancedParentheses.generate(4).size());
}
}
N=0: []
N=1: [()]
N=4 count: 14
What are common mistakes?
Generate-then-filter wastes exponential time. String concatenation instead of StringBuilder creates garbage. Forgetting the deleteCharAt after recursion corrupts the builder.
package com.bank.core;
public class BalancedMistakes {
public static void main(String[] args) {
System.out.println("Mistake 1: generate all 2^(2N), filter -> waste");
System.out.println("Mistake 2: s + '(' instead of StringBuilder");
System.out.println("Mistake 3: no deleteCharAt -> corrupted builder");
}
}
Mistake 1: generate all 2^(2N), filter -> waste
Mistake 2: s + '(' instead of StringBuilder
Mistake 3: no deleteCharAt -> corrupted builder
How is this applied in banking?
At the National Bank of India, the governance team reviews all valid approval workflow nesting shapes for a given number of sub-approval levels. Constrained backtracking generates only well-formed structures, so reviewers examine valid templates without wading through nonsensical patterns.
package com.bank.service;
import java.util.List;
public class GovernanceReview {
public static void main(String[] args) {
int levels = 3;
List<String> shapes = BalancedParentheses.generate(levels);
System.out.println("Approval nesting shapes for " + levels + " levels:");
for (String s : shapes) {
System.out.println(" " + s);
}
}
}
Approval nesting shapes for 3 levels:
((()))
(()())
(())()
()(())
()()()
What should a senior engineer know?
The technique of enforcing validity during construction rather than filtering afterward is a general backtracking optimization that applies to Sudoku, N-Queens, and expression generation. An alternative BFS approach uses a queue of (string, open, close) states. Recognizing the Catalan count signals mathematical maturity.
package com.bank.core;
public class SeniorBalancedNotes {
public static void main(String[] args) {
System.out.println("Pattern: validity as pruning (general backtracking opt)");
System.out.println("Also: Sudoku, N-Queens, valid expressions");
System.out.println("Alt: BFS with queue of (string, open, close)");
System.out.println("Math: Catalan number = C(2N,N)/(N+1)");
}
}
Pattern: validity as pruning (general backtracking opt)
Also: Sudoku, N-Queens, valid expressions
Alt: BFS with queue of (string, open, close)
Math: Catalan number = C(2N,N)/(N+1)
Visual Overview
Backtracking Tree for N=2
──────────────────────────
""
/
(
/ \
(( ()
| |
(() ()(
| |
(()) ()()
Results: "(())", "()()"
Decision at each node:
──────────────────────
Can place '('? → openCount < N
Can place ')'? → closeCount < openCount
Done? → length == 2N → record
Key Takeaway
Balanced Parentheses generates all valid combinations of N pairs using constrained backtracking. I build the string character by character with two counters, placing an open while openCount < N and a close only while closeCount < openCount. The closeCount < openCount invariant guarantees every prefix stays valid, so every leaf is a correct result with no post-generation filtering.
The count of results is the Nth Catalan number, which grows far slower than the 2^(2N) brute-force candidates. For N=10, that is 16796 valid strings versus over a million. Using StringBuilder with append-recurse-deleteCharAt keeps the backtracking efficient without string allocation overhead.
This constrained generation technique, where validity rules act as pruning, is a general optimization pattern that applies to Sudoku, N-Queens, and expression generation. Recognizing the Catalan number connection signals mathematical depth to an interviewer.
At the National Bank of India, I used this to enumerate all valid nested approval workflow shapes for governance review. Each generated template was valid by construction, saving reviewers from examining nonsensical patterns. Explaining the two placement rules, why they keep every prefix valid, and the Catalan count is what shows an interviewer I understand backtracking with invariants.
Remember one sentence: place an open while budget remains, place a close only while closes trail opens, and every string is valid by construction.
---