22. Generate Parentheses

class Solution { public: string available(int left, int right, int n){ // a function to decide at current position, if we can choose left or right or both if (right > left) return "wrong"; else if (left == n){ if (right == n) return "neither"; else return "right"; } else return "both"; } void helper(int left, int right, int n, string & chosen, vector<string> & res) { // left is how many left parenthesis already chosen // right is how many right parenthesis already chosen if (available(left, right, n) == "wrong") return; // do nothing else if (available(left, right, n) == "neither") res.push_back(chosen); // now choose explore unchoose... else if (available(left, right, n) == "right") { chosen.push_back(')'); helper(left, right+1, n, chosen, res); chosen.pop_back(); } else { // can do both chosen.push_back('('); helper(left+1, right, n, chosen, res); chosen.pop_back(); chosen.push_back(')'); helper(left, right+1, n, chosen, res); chosen.pop_back(); } } vector<string> generateParenthesis(int n) { vector<string> res; string chosen = ""; helper(0, 0, n, chosen, res); return res; } };