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 )

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!