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;
}

这会产生正确的输出。我知道面试官(至少在亚马逊)喜欢问你解决方案的时间和空间复杂度。对于时间复杂度，我能够证明该算法在 O(n) 中运行并具有递归关系。我在分析空间复杂度时遇到了麻烦。我这是一个递归解决方案，所以它至少应该是 O(n) 但是在每次递归调用时，我还生成了一个以 n 为界的集合。总空间是 O(n) 因为 n 次递归调用还是 O(n²) 因为设置的大小为每个递归调用 n 绑定(bind) n？

Answer 1

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

这是错误的。平衡括号的序列数由 Catalan numbers 给出。 :这样的序列呈指数级增长。如果您的算法也能正确解决问题，那么它不能是线性的，因为仅输出指数数量的解决方案本身就需要指数时间。

至于内存复杂度，您似乎在递归的每个步骤 n 中存储了 n - 1 的所有解决方案，因此内存复杂度对我来说也是指数级的，加上您创建的其他字符串和您在每个步骤中进行的递归调用，这只会增加复杂性。

您可以在不使用指数内存的情况下解决问题:考虑如何摆脱存储所有以前的序列。