22.括号生成

22. 括号生成

难度 中等

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

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

提示：

• 1 <= n <= 8

DFS

• 结果长度 = 2n

• 开头一定是 (，结尾一定是 )

  • n == 1 时，直接返回 ()

• 记录剩余可用的 ( 和 ) 数目：leftNum，rightNum

  • 当 leftNum > 0 && leftNum == rightNum 时，只能放 (
  • 当 leftNum > 0 时，就能放 (
  • rightNum > 0 当 rightNum != leftNum 时，才能放 )

• 总是一上来先放一个 (，然后使用回溯法

public class _22括号生成 {

List<String> resultList;

char[] selectedArray;

int totalLen; // 结果字符串的总长度

public List<String> generateParenthesis(int n) {

resultList = new ArrayList<>();

// n ≥ 2

totalLen = n << 1; // 2n

selectedArray = new char[totalLen]; // 长度为 2n 的字符数组

dfs(0, n, n);

return resultList;

}

private void dfs(int depth, int leftNum, int rightNum) {

if (depth == totalLen) {

resultList.add(new String(selectedArray));

return;

}

if (leftNum > 0) {

selectedArray[depth] = '(';

dfs(depth + 1, leftNum - 1, rightNum);

}

if (rightNum > leftNum) {

selectedArray[depth] = ')';

dfs(depth + 1, leftNum, rightNum - 1);

}

}

public static void main(String[] args) {

_22括号生成 o = new _22括号生成();

List<String> list = o.generateParenthesis(3);

for (String s : list) {

System.out.println(s);

}

}

}