print all validate parentheses - found mistake in the book
This question is from "Cracking the coding interview" (Fourth Edition) and I think that I found mistake in the answer.
let's take n=3 in the book example you get 4 sequences, but I think there is 5 sequences. ((())), ()(()), ()()(), (()()), (())()
also my solution is much more simple from that in the book
public static ArrayList<String> GetAllNPairsOfParentheses(int n)
{
ArrayList<String> retArray;
if (n==1)
{
retArray=new ArrayList<String>();
retArray.add("()");
return retArray;
}
retArray= GetAllNPairsOfParentheses(n-1);
HashSet<String> hash=new HashSet<String>();
for (String currentPrantheses : retArray)
{
for (int i=0;i<currentPrantheses.length();i++)
{
String currentPranthesesBegin = currentPrantheses.substring(0,i);
String currentPranthesesEnd = currentPrantheses.substring(i);
String newPrantheses= currentPranthesesBegin+"()"+currentPranthesesEnd;
if (!hash.contains(newPrantheses))
{
hash.add(newPrantheses);
}
}
}
retArray=new ArrayList<String>();
for (String currentPrantheses : hash)
{
retArray.add(currentPrantheses);
}
return retArray;
}
You are correct!
- Anonymous July 18, 2014for n=3, 5 is right: (6 choose 3)/4 = 5.
The number is (2n choose n)/(n+1).
Look up catalan numbers on the web.