LeetCode 22：括号生成（Generate Parentheses）解法汇总

更多LeetCode题解

回溯法

class Solution {
public:
	char paren[2] = { '(',')' };
	vector<string> generateParenthesis(int n) {
		vector<string> res;		
		string str;
		for (int i = 0; i < 2 * n; i++) {
			str.push_back('\0');
		}
		backtrack(res, str, 0, n);
		return res;
	}
	void backtrack(vector<string>& res, string &str, int k, int n) {
		if (k >= 2 * n) {
			if(checkall(str))
				res.push_back(str);
		}
		else {
			for (int j = 0; j < 2; j++) {
				str[k] = paren[j];
				if (check(str)) {
					backtrack(res, str, k + 1, n);
				}
				str[k + 1] = '\0';
			}
		}
	}
	bool check(string v) {
		stack<char> sta;
		for (int i = 0; v[i] != '\0'; i++) {
			if (v[i] == '(') {
				sta.push(v[i]);
			}
			else {
				if (!sta.empty()) {
					sta.pop();
				}
				else {
					return false;
				}
			}
		}
		return true;
	}
	bool checkall(string v) {
		stack<char> sta;
		for (unsigned int i = 0; i < v.size(); i++) {
			if (v[i] == '(') {
				sta.push(v[i]);
			}
			else {
				if (!sta.empty()) {
					sta.pop();
				}
			}
		}
		if (sta.empty())
			return true;
		else
			return false;
	}
};