Leetcode #22: Generate Parentheses

Leetcode_0022.cpp

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;
    }
};