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?