โ† Salesforce questions
CodingHard

Generate all valid parentheses for integer N

Filed under Salesforce

Free read 1 of 3

Use 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

  1. Use recursion to build the string. Keep track of open and closed counts.

Solution

O(4^n / sqrt(n)) time, O(n) space

Python
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.