C++ intuitive solution


  • 0
    L
    if (the number of "(" is greater than the number of ")") {
        if (the number of "(" is less than `n`, next character could be '(') {
             the next character could be '('.
        }
        the next character could be ')'.
    }
    
    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            if (n == 0) return res;
            string str("(");
            backtracking(2*n, 1, 0, str, res);
            return res;
        }
        
        void backtracking(int n, int numofleft, int numofright, string str, vector<string> &res) {
            if (str.size() == n) {
                res.push_back(str);
                return;
            }
            if (numofleft >= numofright) {
                if (numofleft < (n >> 1))
                    backtracking(n, numofleft+1, numofright, str+"(", res);
                backtracking(n, numofleft, numofright+1, str+")", res);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.