Java solution with thinking process and LOTS of comment


  • 1
    /*
    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);
            }
        }
    }
    
    

  • 0
    H

    clear explanation!thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.