educative.io

Another approach

Courses
,
#1

We can start with () and in each step three of these things

  1. append ()
  2. prefix ()
  3. enclose in ( … )

ex.
start - ()
iteration 1 - ()(), (()) [in this case prefix and appending with () results in same string ()()]
iteration 2 - ()()(), (()()), (())(), ()(()) ((()))

code

public static List<String> generateValidParentheses(int num) {

    if(num == 0)

      return Collections.emptyList();

    List<String> result = new ArrayList<>();

    

    List<String> previouslyGenerated = new ArrayList<>();

    previouslyGenerated.add("()");

    for(int i = 1; i < num; i++) {

      int size = previouslyGenerated.size();

      Set<String> newSet = new HashSet<>();

      for(int j = 0; j < size; j++) {

        newSet.add("()" + previouslyGenerated.get(j));

        newSet.add(previouslyGenerated.get(j) + "()");

        newSet.add(wrapWithParanthesis(previouslyGenerated.get(j)));

      }

      previouslyGenerated = new ArrayList<>(newSet);

    }

    return previouslyGenerated;

  }
1 Like
#2

yep, I got this same solution :metal:

1 Like
#3

I got the same solution.
@Viraj_Bhosle What did you get as Runtime + Memory complexity for this solution?

#4

@C123 @Lev Unfortunately, this is failing on leetcode for input 4. Not generating the combination “(())(())”. Got to check what’s wrong. Please share the solution, if your is correct and matches my solution.

#5

@Viraj_Bhosle you are right, it fails on leetcode for input 4, will check how to fix it later. Thanks for pointing out!