[LeetCode] Generate Parentheses

Generate Parentheses

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:

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

Solution: Backtracking.

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

public class Solution { private ArrayList<String> result; private char[] chars; private void genParen(int leftRem, int rightRem, int i) { if (leftRem > rightRem || leftRem < 0) { return; } if (leftRem == 0 && rightRem == 0) { result.add(String.valueOf(chars)); return; } chars[i] = '('; genParen(leftRem - 1, rightRem, i + 1); chars[i] = ')'; genParen(leftRem, rightRem - 1, i + 1); } public List<String> generateParenthesis(int n) { result = new ArrayList<String>(); chars = new char[2 * n]; genParen(n, n, 0); return result; } }