### James S. Plank

Wed May 10 01:36:53 EDT 2017
This problem screams dynamic programming, and the constraints are so small, that you don't really need to be too creative. To wit:
• The obvious base case is the empty string. There's one way to get this string.
• For the recursion, try every letter from s[1] to s[s.size()-1]. If you remove the first character and this character, and you are left with a legal string, then call countWays() recursively, and add this to the solution.
So, loop i from 1 to s.size()-1, and create a new string composed of the characters from 1 to i-1 and from i+1 to the end of the string. Test this for legality. If it's legal, call countWays() recursively on it, and add the return value to a running sum of return values. When you're done with the loop, return the total. Of course, this is a dynamic program, so you should memoize.

Let's use example 0 from the writeup to illustrate. The string is:

```( ) ( ) ( ) ( ) ( )
```
Now, we'll run through all of the characters, starting with s[1], and if the character is a right paren, then we build a new string where we delete s[0] and the right paren, test for legality, and if legal, make the recursive call. Let's use the following table to see the strings and recursive calls:

 i String with deleted characters in orange Legal and do recursion? 1 ( ) ( ) ( ) ( ) ( ) Yes 3 ( ) ( ) ( ) ( ) ( ) No 5 ( ) ( ) ( ) ( ) ( ) No 7 ( ) ( ) ( ) ( ) ( ) No 9 ( ) ( ) ( ) ( ) ( ) No

It should be pretty clear that this one's answer is going to be one. Let's try example 2 to show one with more recursion. Here's the string:

```( ( ( ) ( ) ( ) ) )
```
And here's the table:

 i String with deleted characters Legal and do recursion? 3 ( ( ( ) ( ) ( ) ) ) Yes 5 ( ( ( ) ( ) ( ) ) ) Yes 7 ( ( ( ) ( ) ( ) ) ) Yes 8 ( ( ( ) ( ) ( ) ) ) Yes 9 ( ( ( ) ( ) ( ) ) ) Yes

If you still need some more detail, here's example two run to completion -- for each string, I'll print the recursive calls that it makes, and the final values:

```s:         ()  Returns  1   Calls: :1
s:       (())  Returns  2   Calls: ():1 ():1
s:     ((()))  Returns  6   Calls: (()):2 (()):2 (()):2
s:       ()()  Returns  1   Calls: ():1
s:     (()())  Returns  4   Calls: (()):2 ()():1 ()():1
s:   ((()()))  Returns 18   Calls: ((())):6 (()()):4 (()()):4 (()()):4
s:     ()(())  Returns  2   Calls: (()):2
s:   (()(()))  Returns 12   Calls: ((())):6 ()(()):2 ()(()):2 ()(()):2
s:     ()()()  Returns  1   Calls: ()():1
s:   (()()())  Returns  8   Calls: (()()):4 ()(()):2 ()()():1 ()()():1
s: ((()()()))  Returns 54   Calls: ((()())):18 (()(())):12 (()()()):8 (()()()):8 (()()()):8
```

If running time were an issue, there are many things you could do. One of the fun ones would be to turn the string into a linked list, because that way, "deleting" a character would be more efficient. However, nothing like that is necessary -- you can solve this by constructing the new string on the fly.
Commented solution in Solution.cpp.

 ```/* Topcoder SRM 714, D2, 500-pointer. RemovingParenthesis James S. Plank Mon May 15 15:56:16 EDT 2017 */ #include #include #include #include #include using namespace std; class RemovingParenthesis { public: int countWays(string s); map C; }; int RemovingParenthesis::countWays(string s) { int i, j; int legal; // Is the new string legal? int level; // Use this to keep track of nesting level when testing for legality. int total; // Sum of all recursive calls. string s2; // The string that we build from deleting characters 0 and i. /* Base case -- return 1 for the empty string. */ if (s.size() == 0) return 1; /* Check the cache to see if you've solved this one already. */ if (C.find(s) != C.end()) return C[s]; total = 0; /* Run through each character starting with i=1. If the character is a right paren, then construct s2 by deleting characters 0 and i. Use substr() to do this. */ for (i = 1; i < s.size(); i++) { if (s[i] == ')') { s2 = (s.substr(1, i-1) + s.substr(i+1)); /* Now test s2 for legality */ legal = 1; level = 0; for (j = 0; j < s2.size(); j++) { if (s2[j] == '(') { level++; } else { level--; } if (level < 0) legal = 0; } /* The constraints guarantee that level will = 0 at the end of the loop above. If they didn't, I should make sure that level equals 0 here. */ /* If it's legal, then make the recursive call. */ if (legal) total += countWays(s2); } } /* Memoize and return at the end. */ C[s] = total; return total; } ```