在 Java 中使用递归的字符串排列

Question

我遇到了这篇文章，它非常努力地解释了打印所有字符串的递归解决方案。

public class Main {
    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
            System.out.println(prefix);
        else {
            for (int i = 0; i < n; i++)
                permutation(prefix + str.charAt(i),
                        str.substring(0, i) + str.substring(i + 1));
        }
    }

    public static void main(String[] args) {
        permutation("", "ABCD");
    }
}

但是当我们开始从堆栈中弹出时，我仍然无法获得该部分。例如，递归一直进行到permutation("ABCD","")，在基本情况下遇到并打印ABCD。但是现在会发生什么？我们permutation("ABC","D")从函数调用堆栈中弹出。我们如何处理这个等等？

有人可以帮忙解释一下吗？

另外，我需要一些有关此时间复杂度的指针。不像完整的计算，而是一些提示。

Answer 1

更简单的例子：permutation("", "ABC")，将空字符串表示为*：

* ABC + A BC + AB C - ABC *
      |      |
      |      ` AC B - ACB *
      |
      + B AC + BA C - BAC *
      |      |
      |      ` BC A - BCA *
      |
      ` C AB + CA B - CAB *
             |
             ` CB A - CBA *

请注意，这看起来像一棵侧放的树。确实，它叫一棵树。当我们开始时，我们会进入("A", "BC")状态；我们继续打电话("AB", "C")，最后("ABC", "")。在这里我们打印我们的输出。然后我们记得还有未完成的事情，我们返回到一个循环，但是上一层的循环只有一个循环。所以我们也完成了，并返回到("A", "BC")水平；中有两个元素"BC"，我们只完成了"B"，所以现在"C"轮到了：我们调用("AC", "B")，然后调用("ACB", "")。现在下面的所有循环("A", "BC")都已完成...但是等等，还有工作要做！因为("", "ABC")还有两封信需要处理。就这样，一个分支接一个分支地进行，这就是我们通常所说的“深度优先搜索”。

每个级别都有一个循环。循环缩小了（我们在左侧的粗分支中迭代 3 次，然后在下一级迭代 2 次，然后仅迭代一次），但仍然存在循环。所以总的来说，我们进行n * (n - 1) * (n - 2) * ... * 2 * 1迭代。O(N!)？