题解 | #括号生成#

package com.hhdd;

import java.util.ArrayList;

/**
 * 给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
 * 例如，给出n=3，解集为：
 * "((()))", "(()())", "(())()", "()()()", "()(())"
 *
 * @Author 
 * @Date 2022/3/26 21:39
 */
public class 括号生成 {
    /**
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis(int n) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        solution(n, n, 0, 0, "", res);
        return res;
    }

    /**
     * @param n1  标识未出'('的数量
     * @param n2  标识未出')'的数量
     * @param m1  标识已出'('的数量
     * @param m2  标识已出'）'的数量
     * @param cur 当前字符串
     * @param res 存放结果
     */
    public void solution(int n1, int n2, int m1, int m2, String cur, ArrayList<String> res) {
        // 如果 n1=0，说明结束，剩下的全得是 )
        if (n1 == 0) {
            while (n2 > 0) {
                n2--;
                cur += ')';
            }
            res.add(cur);
            return;
        }
        // 1 如果 m1 = m2，必然只能出(
        if (m1 == m2) {
            solution(n1 - 1, n2, m1 + 1, m2, cur + "(", res);
        } else {
            solution(n1 - 1, n2, m1 + 1, m2, cur + "(", res);
            solution(n1, n2 - 1, m1, m2 + 1, cur + ")", res);
        }
    }

    public static void main(String[] args) {
        括号生成 demo = new 括号生成();
        ArrayList<String> strings = demo.generateParenthesis(10);
        System.out.println("strings = " + strings);
    }

}