What is the space complexity of this algorithm?

Question

This is problem 9.6 from Cracking the Coding Interview (5^th edition)

Implement an algorithm to print all valid combinations of n-pairs of parenthesis
EXAMPLE
Input: 3
Output:"((())), (()()), (())(), ()(()), ()()()"

Here is the algorithm I implemented(in Java)

private static Set<String> getAllComb(int n) {
      Set<String> allPoss = new HashSet<String>();
      if(n>0) {
          if(n==1) {
              allPoss.add("()");
          } else {
              Set<String> before = getAllComb(n-1);
              for(String phrase: before) {
                  int length = phrase.length();
                  for(int start = length - 2; start>=0; start--) {
                      if(phrase.charAt(start) == '(') {
                          String phraseToConsider = phrase.substring(0, start+1) + "()" +
                               phrase.substring(start + 1);
                          if(!allPoss.contains(phraseToConsider)){
                              allPoss.add(phraseToConsider);
                          }
                      }
                  }
                  String phraseToConsider = "()" + phrase.substring(0);
                  if(!allPoss.contains(phraseToConsider)){
                      allPoss.add(phraseToConsider);
                  }
              }
          }
      }
      return allPoss;
}

This produces the correct output. I know that interviewers(at least at Amazon) love to ask you the time and space complexity of your solution. For time complexity, I was able to show that the algorithm runs in O(n) with a recurrence relation. I am having trouble with analyzing the space complexity. I this is a recursive solution so it should be at least O(n) But at each recursive call, I am also generating a set that is bounded by n. Would the total space be O(n) because of the n recursive calls or is it O(n²) because of the set size of bound n for each recursive call n?

Answer 1

For time complexity, I was able to show that the algorithm runs in O(n) with a recurrence relation

This is wrong. The number of sequences of balanced parentheses is given by the Catalan numbers: there are exponentially many such sequences. Your algorithm cannot be linear if it is also correctly solving the problem, because just outputting an exponential number of solutions is itself taking exponential time.

As for the memory complexity, you seem to store all solutions for n - 1 at each step n of your recursion, so the memory complexity also looks exponential to me, plus the other strings you create and recursive calls you make at each step, which can only add to the complexity.

You can solve the problem without using exponential memory: think about how you can get rid of storing all previous sequences.