Looking for modification


  • 3
    A

    My answer using recursion result in a wrong answer:"((()))","((()())","((()()()","(()(())","(()(()()"
    The problem lies in the position that the function being called back,where the string s has added a "(" to itself.I couldn't find any method to modify the code except using a char array instead of string.
    Here's my code

    class Solution {
    public:
    	void recursion(int l,int r,vector<string>& v,string s)
    	{
    		if(l>r)return;
    		if(l)
    		{s+="(";recursion(l-1,r,v,s);}
    		if(r)
    		{s+=")";recursion(l,r-1,v,s);}
    		if(!(l||r)) v.push_back(s);
    	}
    	vector<string> generateParenthesis(int n) 
    	{
    		if(!n)return vector<string>(1,"");
    		if(n==1)return vector<string>(1,"()");
    		vector<string> result;
    		recursion(n,n,result,"");
    		return result;
    	}
    };

  • 6
    Z

    When you called back from the recursion for the left part, the String s is already changed for the next recursion for the right part . So you need to change s back.

    void recursion(int l, int r, vector<string>& v, string s)
    {
    	if (l>r) return;
    	if (l)
    	{
    		s += "("; recursion(l - 1, r, v, s);
    		s = s.substr(0, s.length()-1);
    	}
    	if (r)
    	{
    		s += ")"; recursion(l, r - 1, v, s);
    		s = s.substr(0, s.length()-1);
    	}
    	if (!(l || r)) v.push_back(s);
    }
    

    In other way, you can pass a new parameter for the recursion, not change the original String.

    void recursion(int l, int r, vector<string>& v, string s)
    {
    	if (l>r) return;
    	if (l)
    	{
    		recursion(l - 1, r, v, s + "(");
    	}
    	if (r)
    	{
    		recursion(l, r - 1, v, s + ")");
    	}
    	if (!(l || r)) v.push_back(s);
    }
    

Log in to reply
 

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