Permutations
franklinqin0 DFSBacktracking
# Solution
# Backtracking 1
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(nums, path):
if not nums:
res.append(path)
for i in range(len(nums)):
dfs(nums[:i] + nums[i+1:], path + [nums[i]])
dfs(nums, [])
return res
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# Backtracking 2
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def dfs(fst):
# if all integers are used up
if fst == n:
res.append(nums[:])
for i in range(fst, n):
# place i-th integer first in the current permutation
nums[fst], nums[i] = nums[i], nums[fst]
# use next integers to complete the permutations
dfs(fst + 1)
# backtrack
nums[fst], nums[i] = nums[i], nums[fst]
dfs(0)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18