0022-generate-parentheses.java

packagearrays;

importjava.util.ArrayList;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Stack;

publicclassSolution {

publicstaticvoidmain(String[] args) {
Solutionsol = newSolution();
sol.generateParenthesis(3);
 }

Stack<Character> stack = newStack<>();
List<String> res = newArrayList<>();

publicList<String> generateParenthesis(intn) {
backtrack(0, 0, n);
returnres;
 }

privatevoidbacktrack(intopenN, intclosedN, intn) {
if (openN == closedN && closedN == n) {
Iteratorvale = stack.iterator();
Stringtemp = "";
while (vale.hasNext()) {
temp = temp + vale.next();
 }
res.add(temp);
 }
if (openN < n) {
stack.push('(');
backtrack(openN + 1, closedN, n);
stack.pop();
 }
if (closedN < openN) {
stack.push(')');
backtrack(openN, closedN + 1, n);
stack.pop();
 }
 }
}