My simple C++ code, recursion, 3ms with explanation


  • 0
    D

    The basic idea is to do recursion: put n ")" and n"(" in a string so that each substring starting from the beginning has a sum (number of "(" minus number of ")") larger than 0. So at each step, just check nL (number of "(" to be placed) and sum

    1. if nL==0, which means we only need to add nR ")" and the current string is a valid string, then add it to the vector

    2. if nL>0, then add a "(" to cur, and move to the next position

    3. if sum>0, then it is possible to add a ")" at the current position, so do it,

      class Solution {
      public:
      void dfs_gen(vector<string> &res, string cur, int nL, int nR, int sum)
      {
      if(!nL)
      { // only ")" to be added, add them and push to the vector
      string temp(nR, ')');
      res.push_back(cur+temp);
      return;
      }
      dfs_gen(res,cur+"(", nL-1, nR, sum+1); // if some "(" are left, add 1 "(" at the current position
      if(sum>0) dfs_gen(res,cur+")", nL, nR-1, sum-1); // if possible, also try to add ")" at the current position
      }
      vector<string> generateParenthesis(int n) {
      vector<string> res;
      string cur;
      int i, j, len;
      if(n>0)
      {
      dfs_gen(res, "", n, n, 0);
      }
      return res;
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.