Question
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Stats
| Frequency | 4 |
| Diffficulty | 3 |
| Adjusted Difficulty | 2 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Solution
Very standard permutation search. You can read more from this link.
My code
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
if (n == 0) {
return ans;
}
helper(ans, "", n, n);
return ans;
}
private void helper(List<String> ans, String path, int left, int right) {
if (left == 0 && right == 0) {
ans.add(path);
return;
}
// add either left or right parenthese
if (left > 0) {
helper(ans, path + "(", left - 1, right);
}
if (right > left) {
helper(ans, path + ")", left, right - 1);
}
}
}