[Leetcod] Generate Parentheses 产生括号

java 3 2016-02-29 13:03
女装

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<String> res = new LinkedList<String>();
    
    public List<String> 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:如果想把生成的括号加上缩进来格式化怎么办?
A:将原先if(left == 00 && right == 0)里面替换为:

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('}');
    }
}
女装
文章评论