c++ solution with less than 3ms


  • 0
    B

    Besides traditional backtracking, I found another solution here.
    The basic thinking is to determine the certain range for each '(' insertion.
    The code is listed as follows,

        vector<string> generateParenthesis(int n) {
            vector<string> ans;
            // initialize a basic template to insert '(' one by one
            string first(2 * n, ')');
            first[0] = '(';
            ans.push_back(first);
            
            // first '(' can only occur in index 0
            // following ith '(' can only occur in certain range, which is from index i to 2*i
            for (int i = 1; i < n; i++) {
                vector<string> temp;
                // list previous insertion, and try next insertion in possible positions
                for (int j = 0; j < ans.size(); j++) {
                    int ind = 0;
                    int num = i;
                    // count previous insertion and decide the start point for next one
                    while (ind < 2 * n && num > 0) {
                        if (ans[j][ind++] == '(') num--;
                    }
                    // possible position for this insertion
                    for (int k = ind; k <= i + i; k++) {
                        string s = ans[j];
                        s[k] = '(';
                        temp.push_back(s);
                    }
                }
                ans = temp;
            }
            return ans;
        }
    

Log in to reply
 

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