Generate Parentheses

最新更新请见：

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

回溯法

复杂度

时间 O(N) 空间 O(N) 递归栈

思路

当我们放置一个新的符号时，我们有两个选择，放置左括号，或者放置右括号，但是按照题意我们最多放置n个左括号，放一个剩余可放置左括号就少一个，但剩余可放置右括号则多了一个。而对于右括号，必须前面放了一个左括号，我们才能放一个右括号。所以我们根据剩余可放置左括号，和剩余可放置右括号，代入递归，就可以求解。

代码

public class Solution {        List
    
      res = new LinkedList
     
      ();        public List
      
        generateParenthesis(int n) {        helper(n, 0, "");        return res;    }        private void helper(int left, int right, String tmp){        // 如果左括号右括号都放完了，则找到一个结果        if(left == 0 && right == 0){            res.add(tmp);            return;        }        // 对于每个位置，我们有两种选择，要么放左括号，要么放右括号        if (left > 0){            helper(left - 1, right + 1, tmp+"(");        }        if (right > 0){            helper(left, right - 1, tmp+")");        }    }}
      
     
    

后续 Follow Up

Q:如果想把生成的括号加上缩进来格式化怎么办？

int level = 0;for(int i = 0; i < tmp.length(); i++){    if(tmp.charAt(i) == '{'){        for(int k = 0; k < level; k++){            System.out.print('\t');        }        System.out.println('{');        level++;    } else {        level--;        for(int k = 0; k < level; k++){            System.out.print('\t');        }        System.out.println('}');    }}