括号生成(Java)

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

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

方法一：回溯法
方法二：深度优先

package com.loo;

import java.util.List;
import java.util.ArrayList;

public class BracketCreate {
    public static void main(String[] args) {
        List<String> list = generateBracket2(3);
        for (String s : list) {
            System.out.println(s);
        }
    }

    public static List<String> generateBracket(int n) {
        List<String> result = new ArrayList<String>();
        if (n <= 0) {
            return result;
        }
        // 深度优先
        dfsBracket("" , n , n , result);
        return result;
    }

    public static void dfsBracket(String bracket , int l , int r , List<String> res) {
        if (l == 0 && r == 0) {
            res.add(bracket);
            return;
        }
        if (l > r) {
            return;
        }
        if (l > 0) {
            dfsBracket(bracket + "(" , l - 1 , r , res);
        }
        if (r > 0) {
            dfsBracket(bracket + ")" , l , r - 1 , res);
        }
    }

    public static List<String> generateBracket2(int n) {
        List<String> result = new ArrayList<String>();
        if (n <= 0) {
            return result;
        }
        bracketCreate(new StringBuilder() , 0 , 0 , n , result);
        return result;
    }

    // 回溯法
    public static void bracketCreate(StringBuilder bracket , int l , int r , int max , List<String> res) {
        if (bracket.length() == max * 2) {
            res.add(bracket.toString());
            return;
        } else {
            if (l < max) {
                bracket.append('(');
                bracketCreate(bracket , l + 1 , r , max , res);
                bracket.deleteCharAt(bracket.length()-1);
            }
            if (r < l) {
                bracket.append(')');
                bracketCreate(bracket , l , r + 1 , max , res);
                bracket.deleteCharAt(bracket.length()-1);
            }
        }
    }
}