Problem statement
Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses.
Return the list of all valid strings.
Examples
Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Input: n = 1
Output: [“()”]
Constraints
1 ≤ n ≤ 8 (typical). Number of valid combinations grows combinatorially (Catalan numbers).
Approach in simple English
The task is to generate every string of length 2n consisting of n opening ‘(‘ and n closing ‘)’ parentheses such that at every prefix the number of ‘(‘ is at least the number of ‘)’. That is the condition for a string to be valid.
A natural and efficient solution is backtracking (depth-first generation) with pruning:
- Build the string step by step. At each step decide whether to place ‘(‘ or ‘)’.
- Keep two counters:
- openUsed: how many ‘(‘ have been placed so far.
- closeUsed: how many ‘)’ have been placed so far.
- You may place ‘(‘ if openUsed < n.
- You may place ‘)’ if closeUsed < openUsed (to keep the prefix valid).
- When the built string reaches length 2n (openUsed == n and closeUsed == n), add it to the result list.
This generates only valid sequences and prunes invalid partial sequences early. The algorithm visits exactly the set of valid combinations plus explores partial states leading to them; it is optimal for this problem.
Alternative approach: iterative generation using a stack or dynamic programming that builds combinations for smaller n and composes them into larger n (less common in interviews). Backtracking is simplest to implement and reason about.
Java code (backtracking solution)
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n <= 0) return result;
StringBuilder sb = new StringBuilder();
backtrack(n, 0, 0, sb, result);
return result;
}
/**
* backtrack
* n - total pairs required
* openUsed - number of '(' used so far
* closeUsed - number of ')' used so far
* sb - current string builder
* result - list to collect valid combinations
*/
private void backtrack(int n, int openUsed, int closeUsed, StringBuilder sb, List<String> result) {
if (openUsed == n && closeUsed == n) {
result.add(sb.toString());
return;
}
// Try to add '(' if we still can
if (openUsed < n) {
sb.append('(');
backtrack(n, openUsed + 1, closeUsed, sb, result);
sb.deleteCharAt(sb.length() - 1); // backtrack
}
// Try to add ')' if it would not lead to invalid prefix
if (closeUsed < openUsed) {
sb.append(')');
backtrack(n, openUsed, closeUsed + 1, sb, result);
sb.deleteCharAt(sb.length() - 1); // backtrack
}
}
// Quick manual test
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.generateParenthesis(1)); // [()]
System.out.println(s.generateParenthesis(2)); // [()(), (())] or similar order
System.out.println(s.generateParenthesis(3)); // 5 combinations
}
}
Notes about the implementation
- StringBuilder is used to avoid creating many immutable String objects; characters are appended and removed during recursion.
- The order of generation is predictable: it tends to produce combinations with earlier ‘(‘ placements first.
- The recursion depth is at most 2n (but effectively n for nested ‘(‘ before ‘)’) so stack usage is safe for typical n ≤ 8.
Dry run (detailed for n = 3)
We will trace the main decisions and show how sequences are formed. The backtracking explores choices in depth-first order; parentheses added are shown as steps.
Initial: n = 3, sb = “”, openUsed = 0, closeUsed = 0.
- Add ‘(‘ (openUsed 1, closeUsed 0) → sb = “(“
1.1 Add ‘(‘ (2,0) → sb = “((“
1.1.1 Add ‘(‘ (3,0) → sb = “(((“
– cannot add ‘(‘ (openUsed == n)
– can add ‘)’ (closeUsed < openUsed): add ‘)’ → sb = “((()”
– (3,1) → can add ‘)’ → sb = “((())” (3,2)
→ add ‘)’ → sb = “((()))” (3,3) -> complete, add “((()))”
– backtrack to “(((“
1.1.2 After backtracking to “((“, try adding ‘)’ earlier:
– add ‘)’ at (2,0) → sb = “(()” (2,1)
1.1.2.1 add ‘(‘ -> sb = “(()(” (3,1)
-> then ‘)’ → “(()()” (3,2) → ‘)’ -> “(()())” (3,3) add
1.1.2.2 backtrack to “(()”, try ‘)’ (allowed since closeUsed < openUsed) -> sb = “(())” (2,2)
-> add ‘(‘ -> “(())(” (3,2) -> add ‘)’ -> “(())()” (3,3) add
1.1.3 Backtrack to “(“…
1.2 After exhausting branches under “((“, back to “(” try adding ‘)’ earlier:
– add ‘)’ at (1,0) → sb = “()” (1,1)
1.2.1 add ‘(‘ -> sb = “()(” (2,1)
1.2.1.1 add ‘(‘ -> sb = “()((” (3,1) -> then “()(())” after closes
1.2.1.2 backtrack etc.
The generated valid combinations (order depends on recursion order) are:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”
Each sequence is produced only when openUsed==3 and closeUsed==3; intermediate invalid sequences are never completed because closeUsed is never allowed to exceed openUsed.
Complexity analysis
Time complexity
- Number of valid combinations equals the nth Catalan number Cn ≈ (4^n) / (n^(3/2) * sqrt(pi)). The algorithm generates each valid combination once and does O(1) work per character (append/remove), so time complexity is proportional to the number of valid sequences times their length: O(Cn * n). Asymptotically this is roughly O((4^n)/sqrt(n)) but for practical n (≤ 8) it is small.
Space complexity
- Recursion stack and StringBuilder use O(n) space. The result list stores O(Cn) strings, each of length 2n, so output space is O(Cn * n).
Edge cases and notes
- n = 0: by problem definition usually return [] (or [“”] depending on variant). The provided code returns [] for n <= 0.
- Large n: number of combinations grows quickly; be mindful of memory if n is large.
- Ordering: the problem does not require a specific order; backtracking order is acceptable.
- If you need iterative generation, you can simulate the same backtracking with an explicit stack storing (current string, openUsed, closeUsed), but recursion is simpler and cleaner.