November 29, 2020
Hello fellow devs π! Itβs a brand-new day and we have a brand new LeetCode problem to solve.
Given n
pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
n
β€ 8Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
The problem description is fairly straight forward (however the solution may not be π). We will be given a number n
which represents the pairs of parentheses, and we need to find out all of their valid permutations. A valid permutation is one where every opening parenthesis (
has its corresponding closing parenthesis )
.
Also, these parentheses can be arranged in any order as long as they are valid. For n = 2
, the valid pairs are β (())
and ()()
. Also, note n = 2
means two (
s and two )
s. The maximum number of pairs can be eight.
This problem description and the analysis above scream Recursion and yes itβs the right way to solve this problem. The naive approach is to generate all the permutations. All sequence of length n
is (
plus all sequences of length n - 1
. The time complexity of this will be O(22n) which is quite large.
What if we generate only those permutations which we know for sure will be valid? It should reduce the time considerably. We can use backtracking for this purpose. There will be three constraints we need to consider here β
n
.n
.To solve this problem, we will follow the below steps -
n
then we will add the string to the list and return.n
, If true, then we will add (
to the current string and increment the count of opening parenthesis.)
to the current string and increment the count of closing parentheses.The time complexity is not easy to understand for this problem. It rests on understanding how many elements are there in the function. This indicates the nth Catalan number which is bounded asymptotically by Cn = 4n/(n). Since each valid sequence has maximum n
steps, therefore, the time complexity will be O(4n/).
Similar as above logic the total space complexity O(4n/) for recursive calls and O(n) for storing the sequence.
To better visualize the solution, Iβd advise you to go copy-paste the code and execute it at Python Tutor.
public class GenerateParentheses {
public List<String> generateParenthesis(int n) {
// Resultant list
List<String> result = new ArrayList<>();
/// Recursively generate parentheses
generateParenthesis(result, "", 0, 0, n);
return result;
}
private void generateParenthesis(List<String> result, String s, int open, int close, int n) {
// Base case
if (open == n && close == n) {
result.add(s);
return;
}
// If the number of open parentheses is less than the given n
if (open < n) {
generateParenthesis(result, s + "(", open + 1, close, n);
}
// If we need more close parentheses to balance
if (close < open) {
generateParenthesis(result, s + ")", open, close + 1, n);
}
}
}
def generate(result: List[str], s: str, _open: int, close: int, n: int):
# Base condition
if _open == n and close == n:
result.append(s)
return
# If the number of _open parentheses is less than the given n
if _open < n:
generate(result, s + "(", _open + 1, close, n)
# If we need more close parentheses to balance
if close < _open:
generate(result, s + ")", _open, close + 1, n)
def generateParenthesis(n: int) -> List[str]:
# Resultant list
result = []
# Recursively generate parentheses
generate(result, "", 0, 0, n)
return result
var generateParenthesis = function (n) {
// Resultant list
const result = [];
// Recursively generate parentheses
generate(result, "", 0, 0, n);
return result;
};
function generate(result, s, open, close, n) {
// Base condition
if (open === n && close === n) {
result.push(s);
return;
}
// If the number of _open parentheses is less than the given n
if (open < n) {
generate(result, s + "(", open + 1, close, n);
}
// If we need more close parentheses to balance
if (close < open) {
generate(result, s + ")", open, close + 1, n);
}
};
fun generateParenthesis(n: Int): List<String> {
// Resultant list
val result: MutableList<String> = ArrayList()
/// Recursively generate parentheses
generateParenthesis(result, "", 0, 0, n)
return result
}
fun generateParenthesis(result: MutableList<String>, s: String, open: Int, close: Int, n: Int) {
// Base case
if (open == n && close == n) {
result.add(s)
return
}
// If the number of open parentheses is less than the given n
if (open < n) {
generateParenthesis(result, "$s(", open + 1, close, n)
}
// If we need more close parentheses to balance
if (close < open) {
generateParenthesis(result, "$s)", open, close + 1, n)
}
}
Congratulations π! We have solved this problem using backtracking.
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πͺ and star β it.
Till next timeβ¦ Happy coding π and Namaste π!