Generate Parentheses Solutions in C++

// Source : https://oj.leetcode.com/problems/generate-parentheses/
// Author : Hao Chen
// Date   : 2014-06-29



#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;


void generator(vector<string>& result, int left, int right, string s);
vector<string> generateParenthesis(int n) {
    
    vector<string> result;
    string s;
    generator(result, n, n, s);
    return result;
}

void generator(vector<string>& result, int left, int right, string s){
    if (left==0 && right==0){
        result.push_back(s);
        return;
    }
    if (left>0){
        generator(result, left-1, right, s+'(');
    }
    if (right>0 && right>left){
        generator(result, left, right-1, s+')');
    }
}
    
void printResult(vector<string>& result)
{
    for(int i=0; i<result.size(); i++){
        cout << result[i] <<endl;
    }
}

int main(int argc, char** argv) 
{
    int n=3;
    if (argc>1){
        n = atoi(argv[1]);
    }
    vector<string> r = generateParenthesis(n);
    printResult(r);
    return 0;
}

#include <vector>
#include <string>
#include <functional>

using std::string; using std::vector;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> vec;
        std::function<void(string, int, int)> addParenthesis = [&](string str, int ln, int rn) {
            if (ln == 0 && rn == 0) vec.push_back(str);
            if (ln > 0) addParenthesis(str+"(", ln-1, rn+1);
            if (rn > 0) addParenthesis(str+")", ln, rn-1);
        };
        addParenthesis("", n, 0);
        return vec;
    }
};

/// Source : https://leetcode.com/problems/generate-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-09-23

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;


/// Generate all permutation and check validation
/// Time Complexity: O(n*2^n)
/// Space Complexity: O(n)
class Solution {

public:
    vector<string> generateParenthesis(int n) {

        string s = string(n, '(') + string(n, ')');
        vector<string> res;
        do{
            if(valid(s))
                res.push_back(s);
        }while(next_permutation(s.begin(), s.end()));
        return res;
    }

private:
    bool valid(const string& s){

        stack<char> stack;
        for(char c: s)
            if(c == '(')
                stack.push(c);
            else if(stack.empty())
                return false;
            else
                stack.pop();
        return true;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/generate-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-09-23

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;


/// Generate all valid permutation directly
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {

public:
    vector<string> generateParenthesis(int n) {

        vector<string> res;
        generate(n, n, "", res);
        return res;
    }

private:
    void generate(int left, int right, const string& cur, vector<string>& res){

        if(left == 0 && right == 0){
            res.push_back(cur);
            return;
        }

        if(left)
            generate(left - 1, right, cur + '(', res);

        if(right && left < right)
            generate(left, right - 1, cur + ')', res);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/generate-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-09-23

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>

using namespace std;


/// Recursively call generateParenthesis for smaller n
/// Time Complexity: O(2^n)
/// Space Complexity: O(2^n)
class Solution {

public:
    vector<string> generateParenthesis(int n) {

        if(n == 0)
            return {};

        vector<string> res;
        for(int i = 0; i <= n - 1; i ++){
            vector<string> left = generateParenthesis(i);
            if(left.size() == 0) left.push_back("");
            vector<string> right = generateParenthesis(n - i - 1);
            if(right.size() == 0) right.push_back("");
            for(const string& l: left)
                for(const string& r: right)
                    res.push_back("(" + l + ")" + r);
        }
        return res;
    }
};


void print_vec(const vector<string>& vec){
    for(const string& s: vec)
        cout << s << " ";
    cout << endl;
}

int main() {

    print_vec(Solution().generateParenthesis(1));
    print_vec(Solution().generateParenthesis(2));
    print_vec(Solution().generateParenthesis(3));

    return 0;
}

/// Source : https://leetcode.com/problems/generate-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-09-23

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>

using namespace std;


/// Memory Search
/// Time Complexity: O(2^n)
/// Space Complexity: O(2^n)
class Solution {

private:
    vector<vector<string>> res;

public:
    vector<string> generateParenthesis(int n){

        res.clear();
        for(int i = 0; i <= n; i ++)
            res.push_back(vector<string>());
        return generate(n);
    }

private:
    vector<string> generate(int n) {

        if(n == 0)
            return {};

        if(res[n].size() != 0)
            return res[n];

        for(int i = 0; i <= n - 1; i ++){
            vector<string> left = generate(i);
            if(left.size() == 0) left.push_back("");
            vector<string> right = generate(n - i - 1);
            if(right.size() == 0) right.push_back("");
            for(const string& l: left)
                for(const string& r: right)
                    res[n].push_back("(" + l + ")" + r);
        }
        return res[n];
    }
};


void print_vec(const vector<string>& vec){
    for(const string& s: vec)
        cout << s << " ";
    cout << endl;
}

int main() {

    print_vec(Solution().generateParenthesis(1));
    print_vec(Solution().generateParenthesis(2));
    print_vec(Solution().generateParenthesis(3));

    return 0;
}

/// Source : https://leetcode.com/problems/generate-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-09-23

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>

using namespace std;


/// Memory Search
/// Time Complexity: O(2^n)
/// Space Complexity: O(2^n)
class Solution {

public:
    vector<string> generateParenthesis(int n){

        if(n == 0)
            return {};

        vector<vector<string>> res(n + 1);
        res[0].push_back("");
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= i - 1; j ++)
                for(const string& l: res[j])
                    for(const string& r: res[i - j - 1])
                        res[i].push_back("(" + l + ")" + r);
        return res[n];
    }
};


void print_vec(const vector<string>& vec){
    for(const string& s: vec)
        cout << s << " ";
    cout << endl;
}

int main() {

    print_vec(Solution().generateParenthesis(1));
    print_vec(Solution().generateParenthesis(2));
    print_vec(Solution().generateParenthesis(3));

    return 0;
}