Generate Parentheses – LeetCode Solution [Medium]

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

LeetCode Problem Link

Input

Integer n

Output

all combinations of well-formed parentheses of n pairs of parentheses

Constraints

  • 1 <= n ≤ 8

Sample Input

n = 2

Sample Output

["(())","()()"]

Solution

Approach: Recursion

class Solution {
public:
    
    void solve (int n, int open, int close, int pos, 
                string str, vector<string>& sol) {
        
        if (pos == 2*n) {
            sol.push_back(str);
            return;
        }
        
        if (open < n) {
            str[pos] = '(';
            solve(n, open+1, close, pos+1, str, sol);
        }
        
        if (open > close) {
            str[pos] = ')';
            solve(n, open, close+1, pos+1, str, sol);
        }
        
    }
    
    vector<string> generateParenthesis(int n) {
        string str (2*n, ' ');
        vector<string> sol;
        
        solve (n, 0, 0, 0, str, sol);
        return sol;
    }
};

Time complexity: O(2n)

Leave a Reply

Your email address will not be published.