Problem Statement: Generate Parentheses
Given an integer n, generate all combinations of well-formed parentheses of length 2n. A valid combination of parentheses is one where each opening parenthesis ( is properly closed with a closing parenthesis ).
Example:
Input:
n = 3
Output:
["((()))", "(()())", "(())()", "()(())", "()()()"]
Input:
n = 1
Output:
["()"]
Approach:
The problem can be approached using backtracking, which allows us to explore all possible combinations of parentheses while ensuring that at each step, the number of opening parentheses ( is never less than the number of closing parentheses ).
- Backtracking Approach:
- We maintain a string that builds up the parentheses.
- We can add an opening parenthesis
(as long as the number of opening parentheses used is less thann. - We can add a closing parenthesis
)as long as it doesn’t exceed the number of opening parentheses. This ensures the parentheses are valid. - Once we have used exactly
nopening andnclosing parentheses, we add the combination to the result list.
- Recursive Structure:
- The recursion will have two main parameters:
open_count(the count of opening parentheses used so far) andclose_count(the count of closing parentheses used so far). - We stop when both counts reach
n, and a valid combination is formed.
- The recursion will have two main parameters:
Time Complexity:
- Time Complexity: The number of valid combinations of parentheses is given by the Catalan number CnC_nCn, which is approximately O(4n/n3/2)O(4^n / n^{3/2})O(4n/n3/2). So the time complexity for generating all combinations is roughly O(4n)O(4^n)O(4n).
- Space Complexity: O(n)O(n)O(n) due to the recursive stack and the space needed to store each valid combination.
Code Implementation
C Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void generateParenthesisRecursive(int n, int open_count, int close_count, char* current, char** result, int* returnSize) {
if (open_count == n && close_count == n) {
result[*returnSize] = (char*)malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
return;
}
if (open_count < n) {
current[open_count + close_count] = '(';
generateParenthesisRecursive(n, open_count + 1, close_count, current, result, returnSize);
}
if (close_count < open_count) {
current[open_count + close_count] = ')';
generateParenthesisRecursive(n, open_count, close_count + 1, current, result, returnSize);
}
}
char** generateParenthesis(int n, int* returnSize) {
char** result = (char**)malloc(100 * sizeof(char*)); // Assumption: max result size
char* current = (char*)malloc(2 * n + 1);
*returnSize = 0;
generateParenthesisRecursive(n, 0, 0, current, result, returnSize);
free(current);
return result;
}
int main() {
int returnSize;
char** result = generateParenthesis(3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
free(result);
return 0;
}
C++ Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
backtrack(n, 0, 0, "", result);
return result;
}
private:
void backtrack(int n, int open_count, int close_count, string current, vector<string>& result) {
if (open_count == n && close_count == n) {
result.push_back(current);
return;
}
if (open_count < n) {
backtrack(n, open_count + 1, close_count, current + "(", result);
}
if (close_count < open_count) {
backtrack(n, open_count, close_count + 1, current + ")", result);
}
}
};
int main() {
Solution solution;
vector<string> result = solution.generateParenthesis(3);
for (const string& combination : result) {
cout << combination << endl;
}
return 0;
}
Java Code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(n, 0, 0, "", result);
return result;
}
private void backtrack(int n, int open_count, int close_count, String current, List<String> result) {
if (open_count == n && close_count == n) {
result.add(current);
return;
}
if (open_count < n) {
backtrack(n, open_count + 1, close_count, current + "(", result);
}
if (close_count < open_count) {
backtrack(n, open_count, close_count + 1, current + ")", result);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
List<String> result = solution.generateParenthesis(3);
for (String combination : result) {
System.out.println(combination);
}
}
}
Python Code:
class Solution:
def generateParenthesis(self, n: int):
result = []
self._backtrack(n, 0, 0, "", result)
return result
def _backtrack(self, n: int, open_count: int, close_count: int, current: str, result: list):
if open_count == n and close_count == n:
result.append(current)
return
if open_count < n:
self._backtrack(n, open_count + 1, close_count, current + "(", result)
if close_count < open_count:
self._backtrack(n, open_count, close_count + 1, current + ")", result)
# Example usage
solution = Solution()
print(solution.generateParenthesis(3)) # Output: ['((()))', '(()())', '(())()', '()(())', '()()()']
C# Code:
using System;
using System.Collections.Generic;
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> result = new List<string>();
Backtrack(n, 0, 0, "", result);
return result;
}
private void Backtrack(int n, int open_count, int close_count, string current, List<string> result) {
if (open_count == n && close_count == n) {
result.Add(current);
return;
}
if (open_count < n) {
Backtrack(n, open_count + 1, close_count, current + "(", result);
}
if (close_count < open_count) {
Backtrack(n, open_count, close_count + 1, current + ")", result);
}
}
public static void Main() {
Solution solution = new Solution();
var result = solution.GenerateParenthesis(3);
foreach (var combination in result) {
Console.WriteLine(combination);
}
}
}
JavaScript Code:
javascriptCopy codevar generateParenthesis = function(n) {
const result = [];
function backtrack(current, open_count, close_count) {
if (open_count === n && close_count === n) {
result.push(current);
return;
}
if (open_count < n) {
backtrack(current + "(", open_count + 1, close_count);
}
if (close_count < open_count) {
backtrack(current + ")", open_count, close_count + 1);
}
}
backtrack("", 0, 0);
return result;
};
console.log(generateParenthesis(3)); // Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation:
- Backtracking: We use a recursive approach to explore all possible combinations of parentheses. At each step, we either add an opening parenthesis
'('or a closing parenthesis')', while maintaining the constraint that the number of closing parentheses cannot exceed the number of opening parentheses. - Base Case: Once we have added exactly
nopening andnclosing parentheses, the string is valid, and we add it to the result. - Recursion:
- Add
'('ifopen_count < n. - Add
')'ifclose_count < open_count.
- Add
- Termination: The recursion terminates when both the
open_countandclose_countreachn, indicating that a valid combination has been formed.
Time Complexity:
- Time Complexity: The number of valid combinations of parentheses is given by the Catalan number CnC_nCn, which is approximately O(4^n / n^{3/2}). So the time complexity for generating all combinations is roughly O(4n)O(4^n)O(4n).
- Space Complexity: O(n)due to the recursion stack and the space required to store each combination.
Summary:
This problem can be efficiently solved using backtracking, where we explore all possible combinations of parentheses while ensuring that each combination is valid. This method generates all valid parentheses combinations for a given n in an optimal way.