38. Generate Parentheses
mediumAsked at SalesforceGiven n pairs of parentheses, generate all combinations of well-formed parentheses. Salesforce uses this as a constrained-backtracking problem.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Salesforce loops.
- Glassdoor (2026-Q1)— Salesforce uses this to test backtracking with constraint pruning.
- Blind (2025-09)— Asked after LC 17 to test backtracking depth.
Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Constraints
1 <= n <= 8
Examples
Example 1
n = 3["((()))","(()())","(())()","()(())","()()()"]Example 2
n = 1["()"]Approaches
1. Generate all and filter
Generate all 2^(2n) strings of length 2n with '(' and ')'; keep the valid ones.
- Time
- O(2^(2n) * n)
- Space
- O(2^(2n))
function generateParenthesis(n) {
const result = [];
function gen(s) {
if (s.length === 2 * n) { if (valid(s)) result.push(s); return; }
gen(s + '('); gen(s + ')');
}
function valid(s) {
let bal = 0;
for (const c of s) { bal += c === '(' ? 1 : -1; if (bal < 0) return false; }
return bal === 0;
}
gen('');
return result;
}Tradeoff: Exponential in n. Salesforce wants the pruned version.
2. Backtracking with open/close constraints
Place '(' if open < n; place ')' if close < open. Recurse.
- Time
- O(C(n))
- Space
- O(n) stack
function generateParenthesis(n) {
const result = [];
function dfs(s, open, close) {
if (s.length === 2 * n) { result.push(s); return; }
if (open < n) dfs(s + '(', open + 1, close);
if (close < open) dfs(s + ')', open, close + 1);
}
dfs('', 0, 0);
return result;
}Tradeoff: Prunes invalid branches early. The total number of valid combinations is the nth Catalan number, so the algorithm is asymptotically optimal.
Salesforce-specific tips
Salesforce specifically tests whether you prune via constraints DURING recursion, not after. The (open < n) and (close < open) checks are the entire interview signal. Bonus signal: mention that the count of valid combinations equals the nth Catalan number — knowing this shows depth.
Common mistakes
- Generating all 2^(2n) strings and filtering — exponential and obvious failure.
- Allowing close < open to be flipped — produces things like ')(' which are invalid.
- Forgetting the termination condition s.length === 2 * n — infinite recursion.
Follow-up questions
An interviewer at Salesforce may pivot to one of these next:
- Valid Parentheses (LC 20) — checking, not generating.
- Longest Valid Parentheses (LC 32) — hard.
- Different Ways to Add Parentheses (LC 241).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
What's the time complexity exactly?
The nth Catalan number, which is C(2n, n) / (n+1) ~ 4^n / (n^1.5). Roughly exponential but tight.
Why prune with (close < open)?
Placing ')' before an open '(' creates an unclosed close, which can never become valid. Pruning here cuts the search space dramatically.