Coder's Cat

LeetCode: Generate Parentheses

2019-12-24

LeetCode Problem

https://leetcode.com/problems/generate-parentheses/

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

For example, given n = 3, a solution set is:

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

Explanation

This is a classic recursive problem, in each recursive loop, we need to add one char ( or ) to current state, but with two limitations:

The number of ( and ) in the final state should be equal n .

In any state, the number of ) should be less or equal to ( .

So we use these parameters in recursive function:

ll : limit number of (

lr : limit number of )

file:img/2019_12_24_generate-parentheses.org_20191224_172618.png

class Solution {
public:

void iter(string state, int ll, int lr, vector<string>& res) {
if(ll == 0 && lr == 0) {
res.push_back(state);
}
if(ll > 0)
iter(state + "(", ll-1, lr, res);
if(lr > ll)
iter(state + ")", ll, lr-1, res);
}

vector<string> generateParenthesis(int n) {
vector<string> res;
iter("", n, n, res);
return res;
}
};

Preparing for an interview? Check out this!