Leetcode练习22 --- Generate Parentheses

1. brute force

class Solution {
    // using the features of char array 
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        // n pairs, the length of each combination is 2 * n
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    
    // recursively generate all of the possible combination
    // if the generated combination valid, add it to the result list
    // recursion through the position, it can be ( or )
    public void generateAll(char[] current, int pos, List<String> result){
        // if insert pos == the length of the current, meaning that it is the last position
        if (pos == current.length){
            if(valid(current)){
                // convert the char array into string 
                result.add(new String(current));
            }
            
        }else{
                // if the current insert is not the last element
                // keep recursion
                current[pos] = '(';
                generateAll(current, pos+1, result);
                
                current[pos] = ')';
                generateAll(current, pos+1, result);
        }
    }
    
    // validate the generated combination
    // current is the combination of char array    
    public boolean valid(char[] current){
        int balance = 0;
        for (char c: current){
            if(c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        
        // finally the valid balance should be zero
        return (balance == 0);
    }
}
           

2. Backtracking

class Solution {
    // using the features of valid parentheses
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        backtrack(combinations, "", 0, 0, n);
        return combinations;
    }
    
    
    // backtracking method to generate each possible combination through dfs
    // add a validation mechanism inside the process
    // the method will generate all the valid sequense 
    // max is n
    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2){
            ans.add(cur);
            return;
        }
         // if the number of open bracket greater than max 
        // it is possible to add one more '(', otherwise not 
        if (open < max)
            backtrack(ans, cur + "(", open + 1, close, max);
        
        // if the number of close bracket less than the number of open bracket
        // it is valid to add one more ')', otherwise not.
        if(close < open)
            backtrack(ans, cur + ")", open, close + 1, max);
    }
  

}
           

参考文档

leetcode solution — Generate Parentheses