CodingHard
Generate all valid parentheses for integer N
Filed under Salesforce
Free read 1 of 3Use recursion to build the string. Keep track of open and closed counts.
The question
Given an integer n, generate all combinations of well-formed parentheses.
Constraints
- n >= 0
- Output order does not matter
Examples
- Input
- 2
- Output
- ['(())', '()()']
- Why
- All valid combinations for two pairs.
Approach
Use recursion to build the string. Keep track of open and closed counts.
Add '(' if open < n. Add ')' if closed < open.
When the string length reaches 2*n, add the current string to the result list.
Solution
O(4^n / sqrt(n)) time, O(n) space
def generateParenthesis(n):
res = []
def backtrack(s, open, close):
if len(s) == 2*n: res.append(s); return
if open < n: backtrack(s+'(', open+1, close)
if close < open: backtrack(s+')', open, close+1)
backtrack('', 0, 0)
return res
Tips
- What they are testing: Verify output for n=0 (empty list or empty string) and n=3.
- Common mistake: Generating all permutations and filtering, which is inefficient compared to backtracking.
Related Salesforce questions
Collected from public candidate posts and coding forums. Updated Nov 2026.