Concise recursive C++ solution


  • 196
    K

    The idea is intuitive. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>0. Append the result and terminate recursive calls when both m and n are zero.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            addingpar(res, "", n, 0);
            return res;
        }
        void addingpar(vector<string> &v, string str, int n, int m){
            if(n==0 && m==0) {
                v.push_back(str);
                return;
            }
            if(m > 0){ addingpar(v, str+")", n, m-1); }
            if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
        }
    };

  • 5
    H

    same idea:
    c is the count of left parenthesis
    rc is the count of right parenthesis

    rc should not be bigger than c

    void generateParenthesis(string s, int c, int rc, int n,vector<string>& res)
    {
    	if(c+rc==2*n)
    	{
    		res.push_back(s);
    	}
    	if(c < n)
    	{
    		generateParenthesis(s+"(",c+1,rc,n,res);
    	}
    	if(rc < c)
    	{
    		generateParenthesis(s+")",c,rc+1,n,res);
    	}
    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
    	string s;
    	generateParenthesis(s,0,0,n,res);
    	return res;
    }

  • 22
    J

    Creating new strings will take up too much space. Let's use string references.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> result;
            if (n < 1) return result;
            string parens;
            collect(result, parens, n, n);
            return result;
        }
        void collect(vector<string> &result, string &parens, int left, int right) {
            if (left > right || left < 0) return;
            if (left + right == 0) {
                result.push_back(parens);
                return;
            }
            parens.push_back('(');
            collect(result, parens, left - 1, right);
            parens.pop_back();
            parens.push_back(')');
            collect(result, parens, left, right - 1);
            parens.pop_back();
        }
    };

  • 1
    P

    If you make the string a reference, you can actually get a 3x gain in speed. This solution is only 8ms.

    class Solution {
    public:
        void combs(int n, int sum, string& s, vector<string> &res) {
            if (s.size() >= 2*n) { res.push_back(s); }
            else {
                if (s.size() - sum < n) {
                    s = s + "("; combs(n, sum, s, res); s.resize(s.size() - 1);
                }
                if (s.size() - sum > sum) {
                    s = s + ")"; combs(n, sum+1, s, res);  s.resize(s.size() - 1);
                }
            }
        }
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            string s = "(";
            combs(n, 0, s, res);
            return res;
        }
    };

  • 0
    L

    Cool , thanks for share.


  • 2
    W

    How did you think of this? It is really nice! Thanks for sharing man!


  • 0
    Y

    How did you think of this? It is really nice! Thanks for sharing


  • 4
    S

    share my recursive cpp code,3ms

    class Solution {
        public:
            vector<string> generateParenthesis(int n) {
                vector<string> vec;
                Recursion(vec,"",0,n,n);
                return vec;
            }
    
            void Recursion(vector<string> &vec,string str,int counter,int left,int right){
                if(counter < 0)return;
                if(left == 0 && right == 0) {
                    vec.push_back(str);
                    return;
                }
                if(left){
                    Recursion(vec,str + "(" ,counter + 1,left -1 ,right);
                }
                if(right){
                    Recursion(vec,str + ")" ,counter - 1,left,right - 1);
                }
            }
    };

  • 1
    I

    This is a Java solution using same idea.

    public class Solution {
        public void addPair(List<String> result, char[] solution, int pos, int n, int m) {
            if (n == 0 && m == 0) {
                result.add(new String(solution));
                return;
            }
            if (n > 0) {
                solution[pos] =  '(';
                addPair(result, solution, pos + 1, n - 1, m + 1);
            }
            if (m > 0) {
                solution[pos] = ')';
                addPair(result, solution, pos + 1, n, m - 1);
            }
        }
    
        public List<String> generateParenthesis(int n) {
            if (n == 0) {
                return new ArrayList<String>();
            }
            ArrayList<String> result = new ArrayList<String>();
            char[] solution = new char[n * 2];
            addPair(result, solution, 0, n, 0);
            return result;
        }
    }

  • 44
    P

    Same idea. 'left', represents how many left parentheses remains; 'right' represents how many right parentheses remains. The remaining right parentheses should be larger than left ones.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> ret;
            helper(ret, "", n, n);
            return ret;
        }
        void helper(vector<string> & res, string str, int left, int right){
            if(left == 0 && right == 0){
                res.push_back(str);
                return;
            }
            if(left > 0) helper(res, str + "(", left - 1, right);
            if(right > left) helper(res, str + ")", left, right - 1);
        }
    };

  • 0
    J

    The java version (cleaner):

    public class Solution {
    public List<String> generateParenthesis(int n) {
    	List<String> ans = new ArrayList<>();
    	if (n == 0)
    		return ans;
    	addPair(ans, "", n, 0);
        return ans;
    }
    
    private void addPair(List<String> ans, String s, int n, int m) {
    	if (n == 0 && m == 0) {
    		ans.add(s);
    		return;
    	}
    	if (m > 0) {
    		addPair(ans, s + ")", n, m-1);
    	}
    	if (n > 0) {
    		addPair(ans, s + "(", n-1, m+1);
    	}
    }
    

    }


  • 0
    A

    Whats the runtime of this solution?


  • 0
    R

    tell me time complexity?


  • 0
    W

    I draw the recursion tree. I found the max time complexity may be o(2^n).


  • 0
    K

    Is it kind of a backtracking?


  • 0
    T

    @jinwu s + "x" is a linear operation with allocation and copy executed on every level of the recursion and kept in memory; while solution[pos] = 'x' is a single memory write.


  • 0
    Z

    So beautiful!


  • 0
    N

    How did you think of this? It is really nice! Thanks for sharing this....


  • 0
    A

    why is it correct? Is it because you always call the left '(' before you call ')' ? in other words, there is no need to check if the output is valid?


  • 0

    In your code,if I exchange the position of two lines,the result is wrong,
    can you explain how you think this concise code?
    <D>

    • if(m > 0){ addingpar(v, str+")", n, m-1); } if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
      if(n > 0){ addingpar(v, str+"(", n-1, m+1); } if(m > 0){ addingpar(v, str+")", n, m-1); } </D>

Log in to reply
 

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