22. Generate Parentheses

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution：

总结见：http://www.jianshu.com/p/883fdda93a66
思路：思路：Backtracking，但要受到括号匹配的限制，
即对于open: open < max, 对于close: close < open。

回溯dfs的顺序(perfer '(' first or ')' first)都可以
Time Complexity: 2^n Space Complexity: O(n)

Code：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        StringBuilder cur_res = new StringBuilder();
        backtrack(0, 0, n, cur_res, result);
        return result;
    }
    
    public void backtrack(int open, int close, int max, StringBuilder cur_res, List<String> result) {
        if(cur_res.length() == max * 2) {
            result.add(cur_res.toString());
            return;
        }
        
        //the order of A and B can be changed. (perfer '(' first or ')' first).
        if(open < max) { //A
            cur_res.append("(");
            backtrack(open + 1, close, max, cur_res, result);
            cur_res.deleteCharAt(cur_res.length() - 1);
        }
        if(close < open) { //B 
            cur_res.append(")");
            backtrack(open, close + 1, max, cur_res, result);
            cur_res.deleteCharAt(cur_res.length() - 1);
        }

    }
}