22. Generate Parentheses

, ,

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void helper(int left, int right, string &s, vector<string> &parentheses){
        // cout << "in helper, s = " << s << ", left = " << left << ", right = " << right << "\n";
        if(left == 0 && right == 0){
            // cout << "s = " << s << "\n";
            parentheses.push_back(s);
            return;
        }
        if(left > 0){
            s += "(";
            helper(left - 1, right, s, parentheses);
            s.pop_back();
        }
        if(left < right){
            s += ")";
            helper(left, right - 1, s, parentheses);
            s.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> parentheses;
        string s = "";
        helper(n, n, s, parentheses);
        return parentheses;
    }
};

Interative (Stack)

Inspired by this solution on LeetCode Discuss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> parentheses;
        string s = "";
        vector< tuple<int, int, string> >st = {{n, n, ""}};
        while(!st.empty()){
            auto [l, r, s] = st.back(); 
            st.pop_back();
            if(l == 0 && r == 0){
                parentheses.push_back(s);
                continue;
            }
            
            if(l > 0) st.push_back({l - 1, r, s + "("});
            if(l < r) st.push_back({l, r - 1, s + ")"});
        }
        return parentheses;
    }
};