LeetCode-22-括号生成

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解题思路

方法1、DFS：

深度优先遍历选择左括号和右括号，由于String拼接每次会产生一个新的String对象，所以传入的字符串不会影响其他结果，当左括号>0时，左括号-1进入下一次拼接。只有当左右括号数目相等为n的时候，拼接的括号才是合法的，此时加入到最终结果，返回上一层。当左括号用完了的时候进行右括号的拼接

方法2、回溯：

回溯法基本上和DFS一致，只是这里的回溯需要手动回溯，由于String每次生成一个新的String对象耗时比较多，所以可以用StringBuilder，然而StringBuilder拼接的时候会把上一次的字符记录着，所以在DFS之后需要手动回溯，即删除上一层拼接的字符cur.deleteCharAt(cur.length()-1);

Java代码

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n==0) return res;
        dfs(n,n,"");
        return res;
    }

    public void dfs(int left,int right,String curStr){
        if(left==0&&right==0){
            res.add(curStr);
            return;
        }

        if(left>0){
            dfs(left-1,right,curStr+"(");
        }
        if(right>left){
            dfs(left,right-1,curStr+")");
        }
    }
}

Java代码2

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    public void backtrack(List<String> res,StringBuilder cur,int left,int right,int max){
        if(cur.length()==max*2){
            res.add(cur.toString());
            return;
        }
        if(left<max){
            cur.append('(');
            backtrack(res,cur,left+1,right,max);
            cur.deleteCharAt(cur.length()-1);
        }
        if(right<left){
            cur.append(')');
            backtrack(res,cur,left,right+1,max);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}