Generate Parentheses @LeetCode

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:

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

	package leetcode;
	import java.util.ArrayList;
	/**
	* Solution: Combination problem + BackTracking.
	*
	* My way: add all possibilities to list, then filter them use isValidParenthese, Get result.
	* Actually, We don't need to calculate all possibilities because most of them are not valid.
	*
	* We could use BackTracking to construct string because '(' ')' has internal relation.
	* left > right filter situation there's more ')' than '('
	* We could also start from 0, and then +1 until left,right > 3. doesn't matter.
	*
	* @author jeffwan
	* @date Apr 2, 2014
	*/
	public class GenerateParentheses {
	public ArrayList<String> generateParenthesis(int n) {
	ArrayList<String> result = new ArrayList<String>();
	if (n <= 0) {
	return result;
	}
	helper(result, "", n, n);
	return result;
	}
	private void helper(ArrayList<String> result, String s, int left, int right) {
	if (left > right || left < 0 || right < 0) {
	return;
	}
	if (left == 0 && right == 0) {
	result.add(s);
	return;
	}
	helper(result, s + "(", left - 1, right);
	helper(result, s + ")", left, right - 1);
	}
	}

view raw GenerateParentheses.java hosted with ❤ by GitHub