筆試題35. LeetCode OJ (22)

vczixL+1xLLiytTTw8D9o6zO0rXEtdrSu7e006bKx9Gtu7ejrNLyzqrO0rbU0a27t7HIvc/D9LjQsMmjrMv50tTO0tPD0a27t9C0wcvSu8/Co6y1q8rHztK3os/Wo6xuPTK1xMqxuvK63LzytaW+zdC0s/bBy7T6wuujrLWrysduPTO1xMqxuvK+zdPQtePC6bezwcujrLWxbj00tcTKsbryLS0tLS0tLS3O0rjQvvW088TU0qrVqMHLLi4uCiAgINXiy7XD98HL1eK49su8wreyu9DQo6yx2NDru7vW1su8wrfIpb3izOKjrMv50tTO0rj419S8utK7uPZuJiMyMDU0MDstLS0tLS0tLSBuPTEwMCCjobrDsMmjrM7StcO13bnpoaM8L3A+CjxwPrXduem1xLe9t6jSssrH09C8vMfJtcSjrA=="(' 和 ')' 的數目有限，我們可以利用這一點，所以我使用了left和right兩個計數器，用來統計'(' 和 ')' 的數目，每次給字符串後面添加了一個'(',left 的值就減少1 ------- 當left=0的時候，直接就可以給字符串後面補上right個 ')' ，這就是一種匹配的情況了。

添加了 '(' 完成後遞歸後，我們可以把之前放‘（’的位置放上 ')' 去遞歸。

**需要注意 right > left 在整個過程中要一直成立

因為‘（））’這樣的情況是不允許發生的，不知道大家看懂了沒有。再舉個例子說明一下吧：

假設當前string 中的字符串為 "()" 這個時候，即： left==right 這個時候只能給它後面加上 '(' 而不能是 ')'

但是當string 中的字符串為 "(()" 或者 "()(" 的個時候，此時 right>left 我們可以在最後面添加上 ')' 去遞歸。

不知道上面的講解大家能看懂不，不懂的話，請看看代碼幫助你理解一下吧：

class Solution {
public:
	vector generateParenthesis(int n)
	{
		vector last;
		if (n <= 0)
		{
			return last;
		}
		int left = n - 1, right = n;
		string tmp = "(";
		//遞歸去發現符合條件的情況
		solve(last, tmp, left, right);
		return last;
	}
	
	void solve(vector&last, string tmp, int left, int right)
	{
		if (left == 0)
		{
			while (right)
			{
				tmp.push_back(')');
				--right;
			}
			last.push_back(tmp);
			return;
		}
		tmp.push_back('(');
		solve(last, tmp, left - 1, right);
		if (right > left)
		{//只有這種情況下，才能給tmp的後面加上 ‘)’,否則不行
			tmp.pop_back();
			tmp.push_back(')');
			solve(last, tmp, left, right - 1);
		}
	}
};