2
\$\begingroup\$

The question is as follows: Given a collection of distinct integers, return all possible permutations. Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Here is my backtracking solution for the problem, where I added the num_calls variable to keep track of the number of times that the backtrack function is called recursively.

class Solution:
    def permute(self, nums):
        answer = []
        num_calls = []

        def backtrack(combo, rem):
            if len(rem) == 0:
                answer.append(combo)
            for i in range(len(rem)):
                num_calls.append(1)
                backtrack(combo + [rem[i]], rem[:i] + rem[i + 1:])

        if len(nums) == 0:
            return None
        backtrack([], nums)
        print(len(num_calls))
        return answer

I can't make sense of any of the answers that I have seen thus far for the time and space complexity of this solution.

Some people say its worst case O(n * n!), but looking at the len of num_calls doesn't verify this claim.

For example, for:

test = Solution()
print(test.permute([1, 2, 3]))

length of num_calls = 15, which != n * n! = 3 * (3*2*1) = 18

, for:

test = Solution()
print(test.permute([1, 2, 3, 4]))

length of num_calls = 64, which != n * n! = 4 * (4*3*2*1) = 96.

, and for:

test = Solution()
print(test.permute([1, 2, 3, 4, 5]))

length of num_calls = 325, which != n * n! = 5 * (5*4*3*2*1) = 600

Can someone please explain this in a simplified and easily understandable manner?

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

The number of calls indeed grows slower than \$n*n!\$. Its growth is only \$O(n!)\$. However, number of calls is not the only source of complexity.

Constructing arguments for the recursive call also takes time, and rem[:i] + rem[i + 1:] is on average linear in terms of n. The total complexity therefore is \$O(n*n!)\$, just as some people say.

\$\endgroup\$
1
  • \$\begingroup\$ How is the growth of the number of calls only O(n!)? For each of the examples I showed above, the number of calls is greater than n!. In addition, could you explain a bit more as to why rem[:i] + rem[i + 1:] is on average linear? \$\endgroup\$ May 12, 2020 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.