括号的合法排序

括号的合法排序

问题描述

这个题目说的是,给你 n 对括号,你要返回这 n 对括号的所有合法排列方式

1
2
3
4
5
6
7
8

比如说,n 等于 3 时,合法的排列有 5 个:

((()))
(()())
(())()
()(())
()()()

解题思路

根据上面的描述,可以找到规律,首先先写出n个左括号,然后依次写出右括号。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class  {

public static List<String> getList(int n) {
if (n <= 0) {
return new ArrayList<String>();
}
List<String> resultList = new ArrayList<String>();
genStr(resultList, n, n, "");
return resultList;
}

public static void genStr(List<String> resultList, int left, int right, String str) {
if (left == 0 && right == 0) {
resultList.add(str);
} else {
if (left > 0) {
genStr(resultList, left -1, right, str + "(");
}
if (right > left) {
genStr(resultList, left, right - 1, str + ")");
}
}
}

public static void main(String[] args) {
List<String> resultList = getList(3);
for (String str : resultList) {
System.out.println(str);
}
}
}