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
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?