```
/*
btm up method
n = 0, return list with empty string
n = 1, add the parenthesis to the element in the string "()"
n = 2, "(())", "()()"
n = 3, "((()))","(()())","(())()" , "()(())", "()()()"
Hm...it's not very obvious to see how we can build n = 2 on top of n = 1....
say we have "()", how can we go from "()" to "(()), ()()"?
After a while of thinking, let's try this:
let's say "(" is +1, and ")" is -1. The rule is that:
when you see a left paran, you add 1; when you see a right paran, you minus 1.
you can never go negative, for example, you can't do ")))" then "(((".
for every call we can check if the start value is 0 or not, if it's 0, we have to start with "(", if it's not, we can start with either.
base case: we run out of paranthesis. we add that to the list
*/
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
helper(n, n, 0, "", result);
return result;
}
private void helper(int left, int right, int value, String tempResult, List<String> result){
/*if we run out of both left and right paren*/
if(left == 0 && right == 0){
result.add(tempResult);
return;
}
/*value is greater than 0, next one can be either left or right paren*/
if(value > 0){
if(left > 0){
helper(left - 1, right, value + 1, tempResult + "(", result);
}
if(right > 0){
helper(left, right - 1, value - 1, tempResult + ")", result);
}
/*value is 0, the next one has to be left paran*/
}else{
helper(left - 1, right, value+1, tempResult + "(", result);
}
}
}
```