Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #22: Generate Parentheses
class Solution {
char openingParenthesis = '(';
char closingParenthesis = ')';
vector<string> answer;
void recurse(string &path, int unusedOpen, int unusedClose) {
if (unusedOpen < 0 || unusedClose < 0) { // invalid state.
return;
}
if (unusedOpen > unusedClose) { // path is not well-formed.
// More opening parenthesis than closing means that we used
// more closing parenthesis. This makes the path invalid.
// This condition guarantees that only well-formed parentheses
// will be pushed into the answer.
return;
}
if (unusedOpen == 0 && unusedClose == 0) { // used all parentheses.
answer.push_back(path); // add the current path into the answer.
return;
}
// Possibility 1 = '('.
path.push_back(openingParenthesis); // try '(' possibility.
recurse(path, unusedOpen-1, unusedClose); // recursively solve.
path.pop_back(); // undo '(' possibility so that we can test others.
// Possibility 2 = ')'.
path.push_back(closingParenthesis); // try ')' possibility.
recurse(path, unusedOpen, unusedClose-1); // recursively solve.
path.pop_back(); // undo ')' possibility.
}
public:
vector<string> generateParenthesis(int n) {
// Initially we have n opening and n closing parentheses that are unused.
string path = ""; // empty path in the beginning.
recurse(path,
n, // number of unused opening parentheses.
n); // number of unused closing parentheses.
return answer;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment