Generate Parentheses
Problem Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The problem asks us to generate all combinations of well-formed parentheses for a given number n, where n denotes the number of pairs of parentheses. A recursive approach can be used by considering two main constraints:
- The number of '(' should be less than or equal to n.
- The number of ')' should be less than or equal to the number of '('.
This approach uses a helper function to form parentheses while adhering to these constraints.
Steps:
- Define a helper function that takes the current string, the number of open parentheses, the number of close parentheses, and the result list.
- If the current string's length is equal to 2 * n, add the current string to the result list since we have a valid combination.
- If the number of open parentheses is less than n, append '(' to the current string and recursively call the helper function.
- If the number of close parentheses is less than the number of open parentheses, append ')' to the current string and recursively call the helper function.
Code:
- Time Complexity: O(4^n / √n) - This complexity is derived from the nth Catalan number, which is asymptotically equivalent to 4^n / √n.
- Space Complexity: O(n) - The recursive stack has at most n stacks due to the maximum depth of recursion for valid combinations.
2. Backtracking Approach
Intuition:
Backtracking is a smart way of pruning unnecessary paths early. This approach is similar to the recursive solution but takes advantage of backtracking by maintaining the valid string generation condition. We use an accumulator to build partial solutions and explore candidates.
Steps:
- Use a backtrack function to handle the creation of each string.
- At every call, utilize auxiliary variables to ensure the number of opening and closing brackets adheres to the constraints.
- Build the string incrementally and choose to either continue adding '(' or ')'.
- Whenever the conditions are violated, undo the previous step and attempt the next candidate.
Code:
- Time Complexity: Same as the recursive approach O(4^n / √n)
- Space Complexity: O(n) space due to recursion stack.