algorithm - このアルゴリズムの空間複雑度は?

Question

これは、Cracking the Coding Interview (^第5版)の問題 9.6 です。

括弧の n 対のすべての有効な組み合わせを出力するアルゴリズムを実装します 。
例
入力: 3
出力:"((())), (()()), (())(), ()(()), ( )()()"

これが私が実装したアルゴリズムです（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;
}

これにより、正しい出力が生成されます。インタビュアー (少なくとも Amazon) は、ソリューションの時間と空間の複雑さを質問するのが大好きです。時間の複雑さについては、アルゴリズムがO(n)で実行され、再帰関係があることを示すことができました。スペースの複雑さの分析に問題があります。これは再帰的なソリューションなので、少なくともO(n)である必要がありますが、再帰呼び出しごとに、n で区切られたセットも生成しています。n 回の再帰呼び出しのために総スペースはO(n)になりますか、それとも再帰呼び出し n ごとにバインドされた n のサイズが設定されているため、O(n ² )になりますか?