My simple DFS C++ solution


  • 0
    D

    No trick, just do dfs, each step try to put a "(" if it is available and also try to put a ")" if the current string curP has more "(" than ")" (i.e. Lleft <Rleft). Two variables used : Lleft is the number "(" to be placed, Rleft is the number of ")" to be placed.

    class Solution {
    private:
        void dfs(vector<string> &res, string curP, int Lleft, int Rleft)
        {
            if(Lleft<=0)   res.push_back(curP + string(Rleft, ')'));
            else
            {
                dfs(res, curP + "(", Lleft-1,  Rleft);
                if(Lleft<Rleft) dfs(res, curP + ")", Lleft,  Rleft-1);
            }
        }
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            dfs(res, "", n, n);
            return res;
        }
    };

  • 0
    G

    I think this code will not be accepted. For example, n=2, when curP="((", Lleft = 0, and curP will be pushed into res as "(()" which is invalid form.


  • 0
    D

    Thanks for your comment but I can't agree. In your example, Rleft will be 2, and
    res.push_back(curP + string(Rleft, ')'));
    will put 2 ')' in the string curP to make it as "(())"


  • 0
    E

    Nice code!

    Just want to share my similar solution. By the way, I prefer to call it backtracking rather than DFS :)

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> results;
            backtrack(n, 0, 0, "", results);
            return results;
        }
    private:
        void backtrack(int n, int left, int right, string current, vector<string> &results) {
            if (left == n) {
                current += string(left - right, ')');
                results.push_back(current);
                return;
            }
            backtrack(n, left + 1, right, current + "(", results);
            if (left > right) backtrack(n, left, right + 1, current + ")", results);
        }
    };
    

Log in to reply
 

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