Generate Parentheses

LeetCode Q 22 - 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 : DFS

Code:

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

private void dfs(int n, int left, int right, String curr) {
	if (left > n || right > n || left < right) return;

	if (curr.length() == 2 * n) {
		res.add(curr); return;
	}

	dfs(n, left + 1, right, curr + '(');
	dfs(n, left, right + 1, curr + ')');
	
	return;
}