CODEWITHSUNDEEP
javarecursion
mettleap
mettleap

Reputation: 1410

Generating all valid parenthesis

I want to create all valid parenthesis strings given an input number n. For example, if n=3, output should be as follows:

["((()))","(()())","(())()","()(())","()()()"]

My code for this problem is as follows:

private void allParenthesis(List<String> result, int n){
    if(n == 1){
        result.add("()");
        return;
    }
    allParenthesis(result, n-1);

    List<String> newResult = new ArrayList<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    System.out.println(newResult+" for n:"+n);
    result = new ArrayList<String>(newResult);

}

And I use this function in the following function,

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<String>();

    allParenthesis(result,n);
    return result;
}

But when I input n = 3, I get the following output,

["()"]

Where am I going wrong? Am I missing anything very simple?

Upvotes: 0

Views: 105

Answers (3)

Mohammad C
Mohammad C

Reputation: 1341

You are losing the results that you have created and are not passing it through the recursion. I have fixed it and simplified to one function. Also using an array list will mean there are duplicates. For eg. 

Str = "()";
newResult.add("()"+str); //this will result in ()()
newResult.add(str+"()"); //this will also result in the same

If you want the above results then keep using arraylist. if not i suggest using LinkedHashSet as set dont have duplicates and a linked once so that the order of insertion is maintained. HashSet can be used if you dont care about the ordering of the results.

I have provided both ArrayList and LinkedHashSet versions.

HashSet - No dups

private LinkedHashSet<String> generateParenthesis(int n){
    if(n == 1){
        LinkedHashSet<String> result = new LinkedHashSet<String>();
        result.add("()");
        return result;
    }
    LinkedHashSet<String> result = generateParenthesis(n-1);

    LinkedHashSet<String> newResult = new LinkedHashSet<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    result.addAll(newResult);
    return result;
}

ArrayList - keep dups

private ArrayList<String> generateParenthesis(int n){
    if(n == 1){
        ArrayList<String> result = new ArrayList<String>();
        result.add("()");
        return result;
    }
    ArrayList<String> result = generateParenthesis(n-1);

    ArrayList<String> newResult = new ArrayList<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    result.addAll(newResult);
    return result;
}

You can use this function like so.

LinkedHashSet<String> result = generateParenthesis(3);
System.out.println(result);

Upvotes: 3

Juan
Juan

Reputation: 134

When you do

result = new ArrayList<String>(newResult);

You are updating the variable defined at allParenthesis, the one you passed it from generateParenthesis remains unchanged.

Do this instead

result.clear();
result.addAll(newResult);

Upvotes: 1

Kartik
Kartik

Reputation: 7917

You are discarding your newResult.

Change 

result = new ArrayList<String>(newResult);

to

result.clear();
result.addAll(newResult);

Upvotes: 1

Related Questions