【LeetCode】22.Generate Parentheses

1 问题

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

1.1 实例一

Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

1.2 实例二

Input: n = 1
Output: [“()”]

提示

• 1 <= n <= 8

2 解题思路

本题可以改写为：

现在有2n个位置，每个位置可以放置字符 ( 或者 )，组成的所有括号组合中，有多少个是合法的？

这就是典型的回溯算法提醒，暴力穷举就行了。

不过为了减少不必要的穷举，我们要知道合法括号串有以下性质：

1、一个合法括号组合的左括号数量一定等于右括号数量，这个很好理解。

2、对于一个合法的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

因为从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。

用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，就可以直接套用回溯算法套路框架了。

3 代码

class Solution {
    public List<String> generateParenthesis(int n) {
        // 记录所有合法的括号组合
        List<String> res = new ArrayList<>();
        if(0==n){
            return res;
        }
        // backtrace the path
        StringBuilder track=new StringBuilder();
        //start
        backtrack(n,n,track,res);
        return res;
    }

    private void backtrack(int left, int right, StringBuilder track, List<String> res){
        //open bracket's number is less than the closed one's
        if(left>right){
            return;
        }
        //else both left and  right are less than 0
        if(left<0 || right<0){
            return;
        }
        //all open brackets and closed ones are done
        if(0==left && 0== right){
            res.add(track.toString());
            return;
        }

        //backtrack
        //push a open bracket, then backtrack
        track.append('(');
        backtrack(left-1, right, track, res);
        track.deleteCharAt(track.length()-1);

        //push a closed one, then backtrack
        track.append(')');
        backtrack(left, right-1, track, res);
        track.deleteCharAt(track.length()-1);
    }
}