Loading…

Implement an algorithm to print all valid

 

Our first thought here might be to apply a recursive approach where we build the solution for f(n) by adding pairs of parentheses to f (n-1). That’s certainly a good instinct.

 

Let's consider the solution for n = 3:



(()())	 ((()))	 ()(())



How might we build this from n = 2?



(())    ()()

 

We can do this by inserting a pair of parentheses inside every existing pair of parentheses, as well as one at the beginning of the string. Any other places that we could insert parentheses, such as at the end of the string, would reduce to the earlier cases.

 

So, we have the following:

 

( ()) -> (()()) I* inserted pair after 1st left paren */

-> ((())) /* inserted pair after 2nd left paren */

-> ()(()) /* inserted pair at beginning of string*/

() () -> (())() /* inserted pair after 1st left paren */

-> ()(()) /* inserted pair after 2nd left paren */

-> () () () /* inserted pair at beginning of string*/

 

But wait – we have some duplicate pairs listed. The string () ( ()) is listed twice.

 

If we’re going to apply this approach, we’ll need to check for duplicate values before adding a string to our list.

 

 Set<String> generateParens(int remaining) {

 Set<String> set= new HashSet<String>();

3 if (remaining== 0) {

 set.add("");

 } else {

 Set<String> prev = generateParens(remaining - 1);

 for (String str : prev) {

 for (int i= 0; i < str.length(); i++) {

if (str.charAt(i) == '(') {

String s= insertlnside(str, i);



/*Add s to set if it's not already in there. Note: HashSet

* automatically checks for duplicates before adding, so an explicit

* check is not necessary. */

set.add(s);

 }

 }

 set.add("()" + str);

 }

 }

 return set;

 }



String insertlnside(String str, int leftlndex) {

 String left = str.substring(0, leftlndex + 1);

 String right = str.substring(leftindex + 1, str.length());

 return left + "()" + right;

 }

 

This works, but it’s not very efficient. We waste a lot of time coming up with the duplicate strings.

We can avoid this duplicate string issue by building the string from scratch. Under this approach, we add left and right parens, as long as our expression stays valid.

 

On each recursive call, 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 a left paren, and when can we use a right paren?

 

1. Left Paren: As long as we haven’t used up all the left parentheses, we can always insert a left paren.

2. Right Paren: 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 (i.e., if there are more left parens in use than right parens), then we’ll insert a right paren and recurse.

 

 void addParen(Arraylist<String> list, int leftRem, int rightRem, char[] str,

 int index) {

 if (leftRem < 0 I I rightRem < leftRem) return;// invalid state



 if (leftRem == 0 && rightRem == 0) {/*Out of left and right parentheses */

 list.add(String.copyValueOf(str));

 } else {

 str[index] = '('; // Add left and recurse

 addParen(list, leftRem - 1, rightRem, str, index + 1);



 str[index] = ')'; // Add right and recurse

 addParen(list, leftRem, rightRem - 1, str, index + 1);

 }

 }



 ArrayList<String> generateParens(int count) {

 char[] str = new char[count *2];

 Arraylist<String> list = new Arraylist<String>();

 addParen(list, count, count, str, 0);

 return list;

 }

 

Because we insert left and right parentheses at each index in the string, and we never repeat an index, each string is guaranteed to be unique.


Leave a Comment