题解 | 括号生成

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    static public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<>();
        List<String> list = new ArrayList<>();
        dfs(result, list, n, n);
        return result;
    }

    static public void dfs(ArrayList<String> result, List<String> list, int n, int m) {
        if (n == 0 && m == 0) {
            result.add(getString(list));
            return;
        }
        if (n == m) {
            list.add("(");
            dfs(result, list, n - 1, m);
            list.remove(list.size() - 1);
        } else {
            if (n < m) {
                if (n > 0) {
                    list.add("(");
                    dfs(result, list, n - 1, m);
                    list.remove(list.size() - 1);
                }
                if (m > 0) {
                    list.add(")");
                    dfs(result, list, n, m - 1);
                    list.remove(list.size() - 1);
                }
            }
        }


    }

    static public String getString(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }
}