//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
//
// Related Topics String Dynamic Programming Backtracking
// 👍 13432 👎 511
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
generateNext(result, n, "", n, n);
return result;
}
private void generateNext(List<String> result, int n, String current, int left, int right) {
if (current.length() == 2 * n) {
result.add(current);
return;
}
String currentBack = current;
if (left > 0) {
current = current + '(';
generateNext(result, n, current, left - 1, right);
current = currentBack;
}
if (right > left) {
current = current + ')';
generateNext(result, n, current, left, right - 1);
current = currentBack;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
