I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses. And I found this program (which works perfectly) :
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public static 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;
}
Then, when I was searching for applications of Catalan Numbers, I found a very interresting application here : https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics It saids that:
We can use catalan numbers to form mountain ranges with n upstrokes and n down-strokes that all stay above the original line. The mountain range interpretation is that the mountains will never go below the horizon
Consequently, I tried to reuse the code above to implement a solution to this problem. I'm not sure, but I think that we can reuse this code since it seems that they have the same "logic". Unfortunately, I tried a lot of things to replace the brackets with '/' and '\' but I failed.
I tried to do something like that :
str[count] = '/';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = '\\';
str[count+1] = '\n';
addParen(list, leftRem, rightRem - 1, str, count + 2);
For me, they have the same logic, like in brackets, we add the left bracket '(' EACH time is possible, but for right bracket ')' we add it only if the number of right brackets is greater than the left. We can do the same raisoning here no? We add '/' EACH time is possible but for '\' we have to count the number of '/' before...
Which I found particularly difficult here is how can we insert the new lines here to have all the correct mountains?
Can you help me to reuse this code if it's possible? Or should I start another code from scratch?
