第46题的time complexity

无法理解solution的解释，明明是permutation，它非要从partial permutation说起，没明白？
按我的理解，这里的time complexity取决于recursion的次数，即树里的节点数，这个理解对不？
如果对的话，节点数是不是N + N*(N-1) + N*(N-1)*(N-2) + ... + N!？这个是O(N!)还是O(N * N!)？

如果每个节点的复杂度是 O(1)的话，你这样想是对的。但是这个地方，当recursion终止也就是basecase的时候，因为要复制整个array/list/vector，这个复杂度是O(N) 的，因为要把N个都复制一下。所以只是N!个叶子节点的复杂度就是N*N!，前面所有加起来一定不超过N*N!。所以最终复杂度应该是O(N*N!)

不知道小帅 发表于 2021-2-9 23:07
如果每个节点的复杂度是 O(1)的话，你这样想是对的。但是这个地方，当recursion终止也就是basecase的时候， ...

谢谢！忘了叶子节点上的复制操作 :P