22. 括号生成

题目链接：https://leetcode-cn.com/problems/generate-parentheses/

难度：中等

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

示例：

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

解法一：暴力法

由题意得，一个有n对括号，那么所有字符一共就是2n个，我们可以暴力2n个括号的所有组合，然后筛选出符合条件的。

筛选条件：遍历生成字符串，

• 碰到左括号，就给lNum ++；
• 碰到右括号，就给lNum --；
• 若右括号数量大于左括号直接返回false；
• 遍历完，判断 lNum是否等于0；
  • INum不等于0，返回false；
  • INum等于0，返回true；

代码：

class Solution {
        public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }
}

解法二：回溯法

我们可以利用，上述递归方法，进行剪枝，剪掉不符合条件的分支。

剪枝条件：

• 若添加的右括号数目大于左括号，那么直接剪掉；
• 若左括号数目大于n直接剪掉。

即：

• 当左括号数目小于n时，我们可以添加左括号
• 当右括号数目小于左括号时，我们可以添加右括号

class Solution {
    public List<String> generateParenthesis(int n){
        List<String> result = new ArrayList();
        createStr(0,0,n,new StringBuilder(),result);
        return result;
    }
    
    public void createStr(int l,int r,int n, StringBuilder str,List<String> result) {
        if(str.length() == n*2) {
            result.add(str.toString());
            return;
        }
        if(l<n) {
            str.append("(");
            createStr(l+1, r, n, str, result);
            str.deleteCharAt(str.length()-1);
        }
        if(r<l) {
            str.append(")");
            createStr(l, r+1, n, str, result);
            str.deleteCharAt(str.length()-1);
        }
    }
}