题目

22. 括号生成

题解

本题使用普通的深搜模板即可.

代码

import java.util.*;

public class code22 {

    // public static List<String> generateParenthesis(int n) {
    // ArrayList<String> res = new ArrayList<String>();
    // backtrack(res, "", n, n);
    // return res;
    // }

    // public static void backtrack(ArrayList<String> res, String s, int left_p, int
    // right_p) {
    // if (left_p == 0 && right_p == 0) {
    // res.add(s);
    // return;
    // }
    // if (left_p < 0 || right_p < 0 || left_p > right_p) {
    // return;
    // }
    // backtrack(res, s + "(", left_p - 1, right_p);
    // backtrack(res, s + ")", left_p, right_p - 1);
    // }

    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        dfs(n, n, "", res);
        return res;
    }

    public static void dfs(int left, int right, String prefix, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(prefix);
        }
        if (left > 0) {
            dfs(left - 1, right, prefix + "(", res);
        }
        if (left < right) {
            dfs(left, right - 1, prefix + ")", res);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            List<String> ans = new ArrayList<String>();
            ans = generateParenthesis(n);
            System.out.println(ans);
        }
    }
}

参考

  1. 括号生成——题解一
  2. 括号生成——题解二