[LeetCode]Different Ways to Add Parentheses

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

	class Solution {
	public:
	vector<int> diffWaysToCompute(string input) {
	vector<int> res;
	bool isNum = true;
	for(int i = 0; i < input.size(); ++i)
	{
	if(isOp(input[i]))
	{
	isNum = false;
	auto left = diffWaysToCompute(input.substr(0, i));
	auto right = diffWaysToCompute(input.substr(i + 1));
	for(auto l : left)
	{
	for(auto r : right)
	{
	switch(input[i])
	{
	case '+':
	res.push_back(l + r);
	break;
	case '-':
	res.push_back(l - r);
	break;
	case '*':
	res.push_back(l * r);
	break;
	default:
	break;
	}
	}
	}
	}
	}
	if(isNum)
	return { stoi(input) };
	return res;
	}
	private:
	bool isOp(char c)
	{
	return c == '+' || c == '-' || c == '*';
	}
	};

view raw Different Ways to Add Parentheses.cpp hosted with ❤ by GitHub

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