Generate Parenthesis - unable to pass testcase

#1

Unable to pass last testcase

#2

Hi Koshima,
I am working on your Code will revert Back with necessary information in a while.

#3

@koshimagoyal97
Sorry for the delay,Your code is working fine for 4/5 Cases But giving Wrong Answer for:
n=11.
Yes your code is printing all the generated parenthesis,But it is not printing the desired output in correct order.
for eg: for n=11 last generated parenthesis should be ((((((((((())))))))))).
Your code last generated Output is ((()()((()))(())))()().
Please try to correct your code for this n.(n=11)
If you have tried and given your whole,then we will surely help you to solve this problem.
Thankyou

#4

I ran this code on my IDE and it is giving correct output on n=11 also

#5

@koshimagoyal97
Is your last output same as the desired output provided by me?

#6

Yes it is same as the desired output stated by you.

#7

@koshimagoyal97

ssgenerateparenthesis
ssgenerateparenthesis1386Ă—648 21.7 KB

Please see the last output of your code.

#8

image
image1366Ă—768 59.2 KB

See at my end it is giving correct result.

#9

see in your code there were two major errors :
first you didnt write the backtracking step…after placing opening and closing bracket in output array…you make the call…after the call you need to remove the bracket placed…you can place a null character in place of it…

second the size of output array should be 22 as max we can have 22 characters in our ans

#10

@eklavyabhatia1398
I did as you stated but test case 0 is failing and the problem that was discussed earlier is same as for n=11 my editor is giving right answer but not CB ide is giving wrong answer.

If I do output array size to 22 then I am receiving run-time error.

Modified code:

#11 
import java.util.*;
public class Main {
    static ArrayList<String> list = new ArrayList<>();
    static void generateParenthesis(int idx,int open,int close,int n,char []output){
        //base
        if(idx==2*n){
            // output[idx]='\0';
            String str = new String(output);
            list.add(str);
            return;
        }
        //recursive
        if(open<n){
            output[idx]='(';
            generateParenthesis(idx+1,open+1,close,n,output);
            output[idx]='\0';//backtracking step
        }

        if(close<open){
            output[idx]=')';
            generateParenthesis(idx+1,open,close+1,n,output);
            output[idx]='\0';//backtracking step
        }
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] output = new char[22];//make output array of size 22
        generateParenthesis(0,0,0,n,output);
        for(int i=list.size()-1;i>=0;i--){
            System.out.println(list.get(i));
        }
    }
}