22. Generate Parentheses Leetcode Solution
Generate Parentheses Leetcode Problem :
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example :
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Generate Parentheses Leetcode Solution :
Constraints :
- 1 <= n <= 8
Example 1:
- Input: n = 1
- Output: [“()”]
Intuition :
This problem is one of the classical recursion problems.
For any given n, lets say n = 2, we have to fill four places in our output (“_ _ _ _”). And each of these places can be either filled by an open braces “(” or a closed braces “)”.
Approach :
- Whenever we have count of open brackets equal to the count of close brackets, we have only one choice – that is to use ‘(‘. Because, all the brackets till now have been balanced. And we can not start a new sequence with ‘)’.
- Whenever, count of close bracket is 0, we can only use ‘(‘.
- Whenever, count of open bracket is 0, we can only use ‘)’.
- And for all the remaining cases, we have both the choices.
- We get an answer, when count of open == 0 and count of close == 0.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
void solve(string op, int open, int close, vector< string> &ans){
if(open == 0 && close == 0){
ans.push_back(op);
return;
}
//when count of open and close brackets are same then
//we have only one choice to put open bracket
if(open == close){
string op1 = op;
op1.push_back('(');
solve(op1, open-1, close, ans);
}
else if(open == 0){
//only choice is to put close brackets
string op1 = op;
op1.push_back(')');
solve(op1, open, close-1, ans);
}
else if(close == 0){
//only choise is to use open bracket
string op1 = op;
op1.push_back('(');
solve(op1, open-1, close, ans);
}
else{
string op1 = op;
string op2 = op;
op1.push_back('(');
op2.push_back(')');
solve(op1, open-1, close, ans);
solve(op2, open, close-1, ans);
}
}
vector< string> generateParenthesis(int n) {
int open = n;
int close = n;
vector< string> ans;
string op = "";
solve(op, open, close, ans);
return ans;
}
};
Java
class Solution {
public List< String> generateParenthesis(int n) {
List< String> res = new ArrayList< String>();
recurse(res, 0, 0, "", n);
return res;
}
public void recurse(List< String> res, int left, int right, String s, int n) {
if (s.length() == n * 2) {
res.add(s);
return;
}
if (left < n) {
recurse(res, left + 1, right, s + "(", n);
}
if (right < left) {
recurse(res, left, right + 1, s + ")", n);
}
}
}
Python
def generateParenthesis(self, n: int) -> List[str]:
def dfs(left, right, s):
if len(s) == n * 2:
res.append(s)
return
if left < n:
dfs(left + 1, right, s + '(')
if right < left:
dfs(left, right + 1, s + ')')
res = []
dfs(0, 0, '')
return res
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment