All valid combinations of n-pairs of parentheses

Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.
EXAMPLE:
input: 3 (i.e., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

My initial thoughts:
First of all, the output in the example is not correct. It misses this case: (()()).

  • Base case: n=1, print “()”.
  • Recursion: Suppose we have all permutation of %latex n-1$ parentheses. Then for each permutation, we can insert a pair of parentheses into 2(n-1)+1=2n-1 positions to create a permutation of n parentheses. Of course, we need to check whether this permutation exists or not.

My initial code:

	public static Set<String> allCombinationsOfParentheses(int n) {
		if (n == 1) {
			Set<String> result = new HashSet<String>();
			result.add("()");
			return result;
		} else if (n > 1) {
			Set<String> result = new HashSet<String>();
			String parenthesis = "()";
			Set<String> subResult = allCombinationsOfParentheses(n - 1);
			for (String combination : subResult) {
				for (int i = 0; i <= combination.length(); ++i) {
					String newCombination = combination.substring(0, i)
							+ parenthesis + combination.substring(i);
					result.add(newCombination);
				}
			}
			return result;
		} else {
			return null;
		}
	}

Solution:
We can solve this problem recursively by recursing through the string. On each iteration, we have the index for a particular character in the string. We need to select either a left or a right paren. When can we use left, and when can we use a right paren?

  • Left: As long as we haven’t used up all the left parentheses, we can always insert a left paren.
  • Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we get a syntax error? We will get a syntax error if there are more right parentheses than left.

So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (e.g., if there are more left parens used), then we’ll insert a right paren and recurse.

	public static void printPar(int l, int r, char[] str, int count) {
		if (l < 0 || r < l)
			return; // invalid state
		if (l == 0 && r == 0) {
			System.out.println(str); // found one, so print it
		} else {
			if (l > 0) { // try a left paren, if there are some available
				str[count] = '(';
				printPar(l - 1, r, str, count + 1);
			}

			if (r > l) { // try a right paren, if there’s a matching left
				str[count] = ')';
				printPar(l, r - 1, str, count + 1);
			}
		}
	}

	public static void printPar(int count) {
		char[] str = new char[count * 2];
		printPar(count, count, str, 0);
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: