What is different between these two ways to store string in C++

Question

I have a question about C++ string storing. Wish to know why I got different answers between these two ways.

This is a Leetcode problem #22 Generate Parentheses:

The first one is my final modified answer and finally got the correct answer which accepted on leetcode compiler.

Two ways inputs are same as "2" And answer might be ["(())","()()"]

1. Correct

    class Solution {
public:
    void matchParenthesis(vector<string> &result,string thisResult,int n ,int left , int right){
        //left= 已使用“(”個數 
        
        if(left==n && right==n){
            
            result.push_back(thisResult);
            thisResult="";
            
        }else{
            
            if(left<n && left>=0){
                
                matchParenthesis(result,thisResult+"(",n,left+1,right);
            }
            if(right<left && right<n){
                matchParenthesis(result,thisResult+")",n,left,right+1);
            }
            //cout<<thisResult<<"\n";
        
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> result;
 
        string thisResult;
        matchParenthesis(result,thisResult,n,0,0);

        return result;
    }
};

2. This was my wrong code before accepting.

class Solution {
public:
    void matchParenthesis(vector<string> &result,string thisResult,int n ,int left , int right){
        //left= 已使用“(”個數 
        
        if(left==n && right==n){
            
            result.push_back(thisResult);
            thisResult="";
            
        }else{
            
            if(left<n && left>=0){
                thisResult+="(";
                matchParenthesis(result,thisResult,n,left+1,right);
            }
            if(right<left && right<n){
                thisResult+=")";
                matchParenthesis(result,thisResult,n,left,right+1);
            }
            //cout<<thisResult<<"\n";
        
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> result;
 
        string thisResult;
        matchParenthesis(result,thisResult,n,0,0);

        return result;
    }
};

input:2 and output: ["(())","(()()"]

The different code as below in the "else" section: 1.

 if(left<n && left>=0){
       matchParenthesis(result,thisResult+"(",n,left+1,right);
  }
  if(right<left && right<n){
       matchParenthesis(result,thisResult+")",n,left,right+1);
  }

if(left<n && left>=0){
      thisResult+="(";
      matchParenthesis(result,thisResult,n,left+1,right);
}
if(right<left && right<n){
      thisResult+=")";
      matchParenthesis(result,thisResult,n,left,right+1);
 } 

I desire to know why the first solution parameter in recursion

matchParenthesis(result,thisResult+"(",n,left+1,right);

parameter thisReuslt+"(" is different from Solution 2, which stores "(" into thisResult like thisResult+="("; and then set the second parameter like matchParenthesis(result,thisResult,n,left+1,right);

In my recognition, they are the same between " first insert "(" into the original parameter thisResult " and direct set the parameter "thisResult" +"(". But it seems not the same, I want to know what is different.

Thank you stackoverflow, thank you everyone. Sorry for that poor English.

Answer 1

This question might be an object lesson on why an open mind is important when debugging. Do not focus too much on what you think the problem is. Be open to being wrong and looking for other explanations.

I desire to know why the first solution parameter in recursion

matchParenthesis(result,thisResult+"(",n,left+1,right);

parameter thisReuslt+"(" is different from Solution 2, which stores "(" into thisResult like thisResult+="("; and then set the second parameter like matchParenthesis(result,thisResult,n,left+1,right);

Since you are focused on this parameter (more precisely, "argument"), your confusion is not surprising because you are right – there is no difference in the argument to this recursive call. The difference comes after this function call. If you stay focused on this argument, you might never see the cause of the bug.

After this recursive call to matchParenthesis, the value of thisResult in first solution has not changed, but it has an extra "(" in the second solution. If this was the end of the function, there would be no problem, but there is more code to get through. Execution could still make it to another recursive call. Suppose thisResult was initially "(". In the first solution, the second recursive call is

// thisResult is "("
matchParenthesis(result,thisResult+")",n,left,right+1);
//same as: matchParenthesis(result,"()",n,left,right+1);

In the second solution, this call is

// thisResult is "((".
thisResult+=")";
// thisResult is now "(()".
matchParenthesis(result,thisResult,n,left,right+1);
// same as: matchParenthesis(result,"(()",n,left,right+1);

This, not the first call, is where there is a difference during execution.

Answer 2

Look at the "else" clause in your code. You modify thisResult in the first "if", then you flow into the second "if", but thisResult now has an extra character. With your final, you never modify thisResult.