Description:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Examples:
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]Solution in Python:
To generate all combinations of well-formed parentheses for a given number of pairs nnn, we can use a backtracking approach. The idea is to build the solution incrementally, by adding an open parenthesis ( if we still have one available, or a close parenthesis ) if it would not invalidate the sequence.
Detailed Steps:
- Initialize:
- Create a function that initializes the backtracking process.
- Initialize an empty list to store the valid combinations.
- Backtracking Function:
- This function will take the current string, the number of open and close parentheses used so far.
- If the current string length is 2×n (i.e., all parentheses are used), add the current string to the result list.
- If the number of open parentheses used is less than nnn, add an open parenthesis and call the function recursively.
- If the number of close parentheses used is less than the number of open parentheses used, add a close parenthesis and call the function recursively.
- Base Cases and Constraints:
- Ensure that we do not add more than nnn open parentheses.
- Ensure that we do not add more close parentheses than open parentheses.
Python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(current_string, open_count, close_count):
# If the current string length is equal to 2 * n, it means we have used all parentheses
if len(current_string) == 2 * n:
result.append(current_string)
return
# If we can still add an open parenthesis, add it and recurse
if open_count < n:
backtrack(current_string + '(', open_count + 1, close_count)
# If we can add a close parenthesis without invalidating the sequence, add it and recurse
if close_count < open_count:
backtrack(current_string + ')', open_count, close_count + 1)
result = []
backtrack('', 0, 0) # Start with an empty string and no open or close parentheses used
return resultSolution in Javascript:
JavaScript
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
// Helper function for backtracking
const backtrack = (currentString, openCount, closeCount) => {
// If the current string length is equal to 2 * n, it means we have used all parentheses
if (currentString.length === 2 * n) {
result.push(currentString);
return;
}
// If we can still add an open parenthesis, add it and recurse
if (openCount < n) {
backtrack(currentString + '(', openCount + 1, closeCount);
}
// If we can add a close parenthesis without invalidating the sequence, add it and recurse
if (closeCount < openCount) {
backtrack(currentString + ')', openCount, closeCount + 1);
}
};
const result = []; // Initialize an empty array to store the results
backtrack('', 0, 0); // Start the backtracking process with an empty string and no open or close parentheses used
return result; // Return the array of valid combinations
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>(); // Initialize an empty list to store the results
backtrack(result, "", 0, 0, n); // Start the backtracking process
return result; // Return the list of valid combinations
}
// Helper function for backtracking
private void backtrack(List<String> result, String currentString, int openCount, int closeCount, int max) {
// If the current string length is equal to 2 * n, it means we have used all parentheses
if (currentString.length() == max * 2) {
result.add(currentString); // Add the current valid combination to the result list
return;
}
// If we can still add an open parenthesis, add it and recurse
if (openCount < max) {
backtrack(result, currentString + "(", openCount + 1, closeCount, max);
}
// If we can add a close parenthesis without invalidating the sequence, add it and recurse
if (closeCount < openCount) {
backtrack(result, currentString + ")", openCount, closeCount + 1, max);
}
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
// Method to generate all combinations of well-formed parentheses
public IList<string> GenerateParenthesis(int n) {
List<string> result = new List<string>(); // List to store valid combinations
Backtrack(result, "", 0, 0, n); // Start the backtracking process
return result; // Return the list of valid combinations
}
// Helper method for backtracking
private void Backtrack(List<string> result, string currentString, int openCount, int closeCount, int max) {
// If the current string length is equal to 2 * n, it means we have used all parentheses
if (currentString.Length == max * 2) {
result.Add(currentString); // Add the current valid combination to the result list
return;
}
// If we can still add an open parenthesis, add it and recurse
if (openCount < max) {
Backtrack(result, currentString + "(", openCount + 1, closeCount, max);
}
// If we can add a close parenthesis without invalidating the sequence, add it and recurse
if (closeCount < openCount) {
Backtrack(result, currentString + ")", openCount, closeCount + 1, max);
}
}
}