Leetcode: Generate Parentheses

22. Generate Parentheses

My Submissions

Total Accepted: 70088 Total Submissions: 203144 Difficulty: Medium

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Subscribe to see which companies asked this question

Hide Tags

 Backtracking String

Show Similar Problems

````````````````````````````````````````````````````````````````

Backtracking:

Different from the "combination-Sum", it doesn't need to use the for loop inside the backtracking. 
And the condition to judge it's valid or not:

               if (l<r || len >= n && l != r)return;

               else if (l == r && len == n) { res.push_back(tmp); return; }

/////////////////////////////////////////////

class Solution {

 public:

        void backTrac(vector<string>& res, string & tmp, int l, int r, int len, int n){

               if (l<r || len >= n && l != r)return;

               else if (l == r && len == n) { res.push_back(tmp); return; }

               else{

                      ++len;

                      if (len>n)return;

                      //test '('

                      ++l;

                      tmp.push_back('(');

                      backTrac(res, tmp, l, r, len, n);

                      --l;

                      tmp.pop_back();

                      //test ')'

                      ++r;

                      tmp.push_back(')');

                      backTrac(res, tmp, l, r, len, n);

                      tmp.pop_back();

                      --r;

               }

               return;

        }

        vector<string> generateParenthesis(int n) {

               vector<string> res;

               string tmp;

               int l = 0, r = 0, len = 0, nn = 2 * n;

               backTrac(res, tmp, l, r, len, nn);

               return res;

        }

 };