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:

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

 

想到的就是DFS，backtrace

 

class Solution {        vector
     
       m_strs;    public:        void backtrace(string  str, int leftPaNum, int paNum)        {               if(leftPaNum == paNum && str.size() == 2*paNum)            {                   m_strs.push_back(str);                return;            }               if(leftPaNum == paNum)            {                   str += ")";                backtrace(str, leftPaNum, paNum);            }               else            {                   // left num == right num                if(leftPaNum  == (str.size()-leftPaNum) )                {                       str += "(";                    backtrace(str, leftPaNum + 1, paNum);                }                   else// left num > right num                {                       str += "(";                    backtrace(str, leftPaNum + 1, paNum);                    str.erase(str.end() - 1);                     str += ")";                    backtrace(str, leftPaNum, paNum);                }               }           }           vector
      
        generateParenthesis(int n)        {            m_strs.clear();            string str;            backtrace(str, 0, n);            return m_strs;        }};