LeetCode 46. 全排列
原题链接
中等
作者:
小聂同学
,
2023-11-02 12:33:47
,
所有人可见
,
阅读 51
class Solution:
'''
Backtracking
1. What's the search order?
Enumerate the number in each position
Draw the decision tree
T: O(n*n!)
last level has n! left nodes
A(m,n) = n!/(n-m)!
Total nodes = (n! + n/2 ! + n/3 ! +...)
= n!(1 + 1/2 + 1/6 + 1/24 ...) <= n! * (1 + 1/2 + 1/4 + 1/8 + ...)
= n! * 2(1- (1/2)n) ,when n->inf
= 2n!
Each node, copy will cost O(n)
S: O(n) + O(n*n!)
O(n) Recursion Stack n level
O(n*n!) result list length, n factorial
'''
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False] * len(nums)
def backtrack(nums, path, used) -> None:
if len(path) == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
path.append(nums[i])
backtrack(nums, path, used)
used[i] = False
path.pop()
backtrack(nums, [], used)
return res