Code

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        result.push_back("()");
        if (n == 1) {
            return result;
        }
        return generate(result, 1, n);
    }

    vector<string> generate(vector<string> prev, int cur, int target) {
        vector<string> result;
        for (string s: prev) {
            for (int i=0; i<=s.length(); i++) {
                if (i == 0) {
                    result.push_back("()"+s);
                }else if (i == s.length()){
                    result.push_back(s+"()");
                }else{
                    result.push_back(s.substr(0, i)+"()"+s.substr(i, s.length()));
                }
            }
        }

        std::sort(result.begin(), result.end());
        result.erase(std::unique(result.begin(), result.end()), result.end());

        if (++cur == target) {
            return result;
        }
        return generate(result, cur, target);
    }
};