c++ solution based on combination


  • 0
    B
    the basic idea is to combine different '(' locations, where ith '(' can only be in the interval [i, 2*i], i starting from 0.
    vector<string> generateParenthesis(int n) {
            vector<string> ans;
            string first(2 * n, ')');
            first[0] = '(';
            ans.push_back(first);
            
            // loop for ith '('
            for (int i = 1; i < n; i++) {
                vector<string> temp;
                // loop for previous results and insert next '('
                for (int j = 0; j < ans.size(); j++) {
                    int ind = 0;
                    int num = i;
                    // find the starting position for ith '('
                    while (ind < 2 * n && num > 0) {
                        if (ans[j][ind++] == '(') num--;
                    }
                    
                    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.