MEDIUM NC#24 Stack / Backtracking

22. Generate Parentheses

📖 Problem

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

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Recursive function frames
  • •Push/pop state undo
  • •Pruning branches early

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Backtracking reasoning pattern
  • •Apply Recursion reasoning pattern

💡 Approach

  • → Use backtracking to build all combinations
  • → Track open and close counts
  • → Can add '(' if open < n
  • → Can add ')' if close < open
  • → Recurse until length reaches 2n
  • → Time: O(4^n/sqrt(n)), Space: O(n) for recursion

🛠️ Hints & Pitfalls

Hints

  • •Use backtracking to build all combinations
  • •Track open and close counts
  • •Can add '(' if open < n

Common Pitfalls

  • •Can add ')' if close < open
  • •Recurse until length reaches 2n
  • •Time: O(4^n/sqrt(n)), Space: O(n) for recursion

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
generateParenthesis(3);
Expected:
["((()))", "(()())", "(())()", "()(())", "()()()"]
Test Case 2
Not run
Input:
generateParenthesis(1);
Expected:
["()"]
Test Case 3
Not run
Input:
generateParenthesis(2);
Expected:
["(())", "()()"]

📝 Code Editor

📚 Reference Solution

▼
⌘K Search ⌘↩ Run ⌘S Submit