[算法] - 括号生成

1. 描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())",

出自牛客网: NC26 括号生成

2. 题解

package com.jfp;

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    private ArrayList<String> res;
    public ArrayList<String> generateParenthesis (int n) {
        res = new ArrayList<>();
        recursion(n, n, "");
        return res;
    }

    private void recursion(int left, int right, String s) {
        if(left == 0 && right == 0){
            res.add(s);
        }else{
            if(left > 0){
                recursion(left - 1, right, s + "(");
            }

            if(right > left){
                recursion(left, right - 1, s + ")");
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<String> strings = solution.generateParenthesis(2);
        System.out.println(strings);
    }
}

3. 输出结果

[(()), ()()]