[LeetCode]Different Ways to Add Parentheses

递归的思路就可以做，对于input string的每一个符号，我们递归地计算左半边的所有结果和右半边的所有结果。combine所有左右的结果然后作为当前input string的结果，代码如下：


空间复杂度就是递归的深度, 假设input string有n个数字，那就是O(n)。时间复杂度的话，因为很明显这是Catalan Number（请参考这道题的时间复杂度分析），所以为O(C(n))，C(n)为第n个Catalan Number.