FilesExpand file tree

 master

/

GenerateParentheses.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (34 loc) · 957 Bytes

 master

/

GenerateParentheses.java

Copy path

Top

File metadata and controls

• Code
• Blame

39 lines (34 loc) · 957 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

32

33

34

35

36

37

38

39

import java.util.ArrayList;

/**

* Given n pairs of parentheses, write a function to generate all combinations

* of well-formed parentheses.

*

* For example, given n = 3, a solution set is:

*

* "((()))", "(()())", "(())()", "()(())", "()()()"

*/

public class GenerateParentheses {

public ArrayList<String> generateParenthesis(int n) {

ArrayList<String> ret = new ArrayList<String>();

StringBuilder sb = new StringBuilder();

generateParenthesis(n, 0, 0, 0, sb, ret);

return ret;

}

public void generateParenthesis(int n, int s, int e, int l,

StringBuilder sb, ArrayList<String> ret) {

if (s == n && e == n) {

ret.add(sb.toString());

} else {

if (l > 0 && e < n) {

sb.append(')');

generateParenthesis(n, s, e + 1, l - 1, sb, ret);

sb.deleteCharAt(sb.length() - 1);

}

if (s < n) {

sb.append('(');

generateParenthesis(n, s + 1, e, l + 1, sb, ret);

sb.deleteCharAt(sb.length() - 1);

}

}

}

}