22. Generate Parentheses

Link

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

這題也是列舉所有可能，backtrace法應該最適合。 每次iteration針對 '(' 還有')'這兩個可能去判斷，並往下遞迴找出所有可能。 choose: '(' or ')'，插入 '('的條件式 '('的個數不超過n，插入')'的條件式目前'('的數目比')'的次數小 observe: 把'(' 與 ')'次數更新後帶入下次iteration unchoose: 拿掉剛剛加入的'('or ')' 並更新對應的次數

 public static List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        helper(ret, "", 0, 0,n);
        return ret;
    }

    public static void helper(List<String> ret, String temp, int count, int countEnd , int max){
        if(temp.length() == max*2){
            ret.add(temp);
            temp = "";
            return;
        }

        if(count < max){
            temp += '(';
            count++;
            helper(ret, temp, count, countEnd ,len);
            temp = temp.substring(0, temp.length()-1);
            count--;
        }

        if(count > countEnd){
            temp += ')';
            countEnd++;
            helper(ret, temp, count, countEnd, len);
            temp = temp.substring(0, temp.length()-1);
            countEnd --;
        }

    }