beingsde
Sign In
Back to all DSA patterns
Backtracking / Recursion•Pattern: Backtracking•Medium

Generate parentheses — all valid combinations of n pairs

Problem Intuition & Objective

Generate all strings of n pairs of well-formed parentheses.

Time ComplexityO(4^n / √n) — Catalan number
Optimal
Space ComplexityO(n) recursion
Memory Bounds
Optimal Algorithmic Approach

Backtracking with open/close counters as constraints.

Core Invariants & Edge Cases

  • Track open and close counts; open < n → can add '('; close < open → can add ')'
  • Base case: string length == 2n
  • Produces exactly Catalan(n) strings
Previous ProblemCount inversions in array

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.