The “Generate Parentheses” problem is about creating all combinations of well-formed parentheses for a given number of pairs, n. Each valid combination must have balanced opening and closing parentheses. For example, if n = 3, some valid combinations would be ((())), (()()), (())(), ()(()), and ()()().
Brute-Force Approach
In a brute-force solution, we can generate all possible sequences of 2 * n parentheses and then filter out the valid ones that are balanced. This approach is inefficient but can help us understand the problem.
import java.util.ArrayList;
import java.util.List;
public class GenerateParentheses {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
generateAll(new char[2 * n], 0, result);
return result;
}
private void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (isValid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
private boolean isValid(char[] current) {
int balance = 0;
for (char c : current) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
return balance == 0;
}
}
The brute-force code works by creating all possible 2 * n combinations of parentheses and filtering them for validity. The generateAll method recursively builds each sequence, and the isValid method checks if each sequence has balanced parentheses. Although this approach works, it’s inefficient due to generating many invalid sequences and has high time complexity.
Optimal Solution: Backtracking Approach
The backtracking algorithm is an optimal approach because it only builds valid sequences from the start, which reduces unnecessary work. We can make use of recursion by adding ( when there are open parentheses left and ) when there are more open parentheses placed than closed ones. This recursive approach ensures all generated sequences are valid, eliminating the need for extra validation.
Backtracking is ideal here because it explores each possibility in a structured way, building and abandoning paths as soon as they become invalid. This reduces the number of sequences generated, making it more efficient in both time and space. The characteristics of the problem—generating combinations under specific constraints—make backtracking a natural fit.
Steps of the Algorithm
1. Start with an empty string and add parentheses recursively.
2. Add an open parenthesis if it doesn’t exceed n.
3. Add a closing parenthesis if it doesn’t exceed the count of open parentheses.
4. When the length of the string equals 2 * n, add it to the result list.
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
StringBuilder current = new StringBuilder();
backtrack(result, current, 0, 0, n);
return result;
}
private void backtrack(List<String> result, StringBuilder current, int open, int close, int max) {
if (open == max && close == max) {
result.add(current.toString());
return;
}
if (open < max) {
current.append("(");
backtrack(result, current, open + 1, close, max);
current.deleteCharAt(current.length() - 1);
}
if (close < open) {
current.append(")");
backtrack(result, current, open, close + 1, max);
current.deleteCharAt(current.length() - 1);
}
}
}Line By Line Detailed Explanation
- Create Array List
List<String> result = new ArrayList<>();- Create a list called result to store al the valid combinations of parentheses.
2. StringBuilder
StringBuilder current = new StringBuilder();- StringBuilder allows us to efficiently build strings character by character and modify them in place, which is more memory-efficient than creating a new String with each modification.
3. Run Back Tracking Function
backtrack(result, current, 0, 0, n);
• This line calls the backtrack function, which will recursively build each valid combination of parentheses.
4. Return Result
return result;4. Backtrack Function
private void backtrack(List<String> result, StringBuilder current, int open, int close, int max)- This starts the recursive process of generating valid sequences by passing the necessary initial parameters.
5. Base Case
if (open == max && close == max) {
result.add(current.toString());
return;
}- This checks if the counts of both open and close parentheses have reached max. We add the fully formed valid combination to our output list. This toString() conversion is necessary because StringBuilder does not automatically convert to String when added to a list.
6. Check Open Paretheses
if (open < max) {
current.append("(");
backtrack(result, current, open + 1, close, max);
current.deleteCharAt(current.length() - 1);
}- Checks if the number of open parentheses is less than max.
- Adds an open parenthesis to the current StringBuilder.
- Proceeds with this partial sequence to continue building with the additional open parenthesis.
- we “undo” adding the open parenthesis so that we can try other possible characters in this position (such as a closing parenthesis if allowed). By removing it, we restore current to its state before the recursive call, enabling exploration of other paths.
7. Check Closed Parentheses
if (close < open) {
current.append(")");
backtrack(result, current, open, close + 1, max);
current.deleteCharAt(current.length() - 1);
}- Checks if the number of close parentheses is less than the number of open parentheses.
- Ensures that every close parentheses added has a corresponding open
Why This Algorithm Works Well
• Recursive Structure: By calling backtrack for both open and close parentheses (when conditions allow), this function explores all possible valid sequences in a structured manner.
• Backtracking with StringBuilder: Using append and deleteCharAt on StringBuilder allows efficient addition and removal of characters, minimizing memory usage. This backtracking step enables the algorithm to explore other paths without unnecessary string creation.
• Condition Checks (open < max and close < open): These conditions ensure that only valid parentheses combinations are created. By controlling when open and close parentheses are added, we maintain balance throughout, producing only valid sequences.
This code is efficient because it builds valid sequences without generating invalid ones, making it far faster and more memory-efficient than a brute-force approach. Each recursive path explores only valid options, and backtracking allows us to explore different sequences without extra memory allocations.
