Generate All Parentheses
Print all combinations of balanced parentheses problem
You are given a positive integer n, representing the number of pairs of parentheses. Your task is to generate and return all possible combinations of well-formed (valid) parentheses strings that can be created using exactly n pairs.
A well-formed parentheses string maintains the correct order, meaning every opening parenthesis ( has a corresponding closing parenthesis ) that appears after it.
Output: ["()"]
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: You may return the answer in any order.
Constraints:
- 1 <= n <= 7
Print all combinations of balanced parentheses Solution
Recommendation for Time and Space Complexity –You should aim for a solution as good or better than O(4^n / sqrt(n)) time and O(n) space, where n is the number of parenthesis pairs in the string.
Hints for solving problems
Hint 1 :
A brute force solution would be to generate all possible strings of size 2n and add only the valid strings. This would be an O(n * 2 ^ (2n)) solution. Can you think of a better way? Maybe you can use pruning to avoid generating invalid strings.
Hint 2 :
We can use backtracking with pruning. But what makes a string invalid? Can you think of a condition for this?
Hint 3 :
When the count of closing brackets exceeds the count of opening brackets, the string becomes invalid. Therefore, we can maintain two variables, open and close, to track the number of opening and closing brackets. We avoid exploring paths where close > open. Once the string length reaches 2n, we add it to the result.
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Backtracking Method
- Dynamic Programming Method
1. Brute Force Method
Generate all possible strings of ( and ) of length 2n and filter out the valid combinations by checking if they form well-balanced parentheses, resulting in high time complexity.
- Time complexity: O(2^(2n) * n)
- Space complexity: O(2^(2n) * n)
Code
class Solution {
public:
bool valid(const string& s) {
int open = 0;
for (char c : s) {
open += (c == '(') ? 1 : -1;
if (open < 0) return false;
}
return open == 0;
}
void dfs(string s, vector& res, int n) {
if (s.length() == 2 * n) {
if (valid(s)) res.push_back(s);
return;
}
dfs(s + '(', res, n);
dfs(s + ')', res, n);
}
vector generateParenthesis(int n) {
vector res;
dfs("", res, n);
return res;
}
};
public class Solution {
public boolean valid(String s) {
int open = 0;
for (char c : s.toCharArray()) {
open += c == '(' ? 1 : -1;
if (open < 0) return false;
}
return open == 0;
}
void dfs(String s, List res, int n) {
if (n * 2 == s.length()) {
if (valid(s)) res.add(s);
return;
}
dfs(s + '(', res, n);
dfs(s + ')', res, n);
}
public List generateParenthesis(int n) {
List res = new ArrayList<>();
dfs("", res, n);
return res;
}
}
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def valid(s: str):
open = 0
for c in s:
open += 1 if c == '(' else -1
if open < 0:
return False
return not open
def dfs(s: str):
if n * 2 == len(s):
if valid(s):
res.append(s)
return
dfs(s + '(')
dfs(s + ')')
dfs("")
return res
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
valid(s) {
let open = 0;
for (const c of s) {
open += c === '(' ? 1 : -1;
if (open < 0) return false;
}
return open === 0;
}
/**
* @param {string} s
* @param {string[]}
* @param {number} n
*/
dfs(s, res, n) {
if (s.length === 2 * n) {
if (this.valid(s)) res.push(s);
return;
}
this.dfs(s + '(', res, n);
this.dfs(s + ')', res, n);
}
/**
* @param {number} n
* @return {string[]}
*/
generateParenthesis(n) {
const res = [];
this.dfs("", res, n);
return res;
}
}
2. Backtracking Method
Use recursion with backtracking to build valid parentheses strings by adding ( or ) only when it maintains a well-formed structure, efficiently pruning invalid paths.
- Time complexity: O(4^n / (n)^1/2)
- Space complexity: O(n)
Code
class Solution {
public:
void backtrack(int openN, int closedN, int n, vector<string>& res, string& stack) {
if (openN == closedN && openN == n) {
res.push_back(stack);
return;
}
if (openN < n) {
stack += '(';
backtrack(openN + 1, closedN, n, res, stack);
stack.pop_back();
}
if (closedN < openN) {
stack += ')';
backtrack(openN, closedN + 1, n, res, stack);
stack.pop_back();
}
}
vector generateParenthesis(int n) {
vector res;
string stack;
backtrack(0, 0, n, res, stack);
return res;
}
};
public class Solution {
private void backtrack(int openN, int closedN, int n, List<String> res, StringBuilder stack) {
if (openN == closedN && openN == n) {
res.add(stack.toString());
return;
}
if (openN < n) {
stack.append('(');
backtrack(openN + 1, closedN, n, res, stack);
stack.deleteCharAt(stack.length() - 1);
}
if (closedN < openN) {
stack.append(')');
backtrack(openN, closedN + 1, n, res, stack);
stack.deleteCharAt(stack.length() - 1);
}
}
public List generateParenthesis(int n) {
List res = new ArrayList<>();
StringBuilder stack = new StringBuilder();
backtrack(0, 0, n, res, stack);
return res;
}
}
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = []
res = []
def backtrack(openN, closedN):
if openN == closedN == n:
res.append("".join(stack))
return
if openN < n:
stack.append("(")
backtrack(openN + 1, closedN)
stack.pop()
if closedN < openN:
stack.append(")")
backtrack(openN, closedN + 1)
stack.pop()
backtrack(0, 0)
return res
class Solution {
/**
* @param {number} openN
* @param {number} closeN
* @param {number} n
* @param {string[]} res
* @param {string} stack
*/
backtrack(openN, closedN, n, res, stack) {
if (openN === closedN && openN === n) {
res.push(stack);
return;
}
if (openN < n) {
this.backtrack(openN + 1, closedN, n, res, stack + '(');
}
if (closedN < openN) {
this.backtrack(openN, closedN + 1, n, res, stack + ')');
}
}
/**
* @param {number} n
* @return {string[]}
*/
generateParenthesis(n) {
const res = [];
this.backtrack(0, 0, n, res, '');
return res;
}
}
3. Dynamic Programming Method
Construct valid combinations using previously computed solutions for smaller values of n, combining them in different ways to form well-balanced parentheses for the current n.
- Time complexity: O(4^n/(n)^1/2)
- Space complexity: O(n)
Code
class Solution {
public:
vector generateParenthesis(int n) {
vector> res(n + 1);
res[0] = {""};
for (int k = 0; k <= n; ++k) {
for (int i = 0; i < k; ++i) {
for (const string& left : res[i]) {
for (const string& right : res[k - i - 1]) {
res[k].push_back("(" + left + ")" + right);
}
}
}
}
return res[n];
}
};
public class Solution {
public List generateParenthesis(int n) {
List> res = new ArrayList<>();
for (int i = 0; i <= n; i++) {
res.add(new ArrayList<>());
}
res.get(0).add("");
for (int k = 0; k <= n; k++) {
for (int i = 0; i < k; i++) {
for (String left : res.get(i)) {
for (String right : res.get(k - i - 1)) {
res.get(k).add("(" + left + ")" + right);
}
}
}
}
return res.get(n);
}
}
class Solution:
def generateParenthesis(self, n):
res = [[] for _ in range(n+1)]
res[0] = [""]
for k in range(n + 1):
for i in range(k):
for left in res[i]:
for right in res[k-i-1]:
res[k].append("(" + left + ")" + right)
return res[-1]
class Solution {
/**
* @param {number} n
* @return {string[]}
*/
generateParenthesis(n) {
const res = Array.from({ length: n + 1 }, () => []);
res[0] = [""];
for (let k = 0; k <= n; k++) {
for (let i = 0; i < k; i++) {
for (const left of res[i]) {
for (const right of res[k - i - 1]) {
res[k].push("(" + left + ")" + right);
}
}
}
}
return res[n];
}
}
