Medium
Easy
GeetCode Hub
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
if(n<=0){
return res;
}
int open = 0;
int close = 0;
generateParenthesis(n, open, close, "",res);
return res;
}
private void generateParenthesis(int n, int open, int close, String asf, List<String> res){
if(open == n && close == n){
res.add(asf);
return;
}
if(open > n || close > n){
return;
}
generateParenthesis(n, open+1, close, asf+"(", res);
if(open>close){
generateParenthesis(n, open, close+1, asf+")", res);
}
}
}
This question is a good example of Recursion with Backtracking. if you know how we can leverage the concept of backtracking then it will be an easy question to be solved.
Time Complexity: O(2^n)
Space Complexity: O(n)