-
题目
全排列 思路
使用深度优先&递归方法来做
不断地抽取其中一个数字，剩余数字构成子问题：1+[2,3]、2+[1,2]、3+[1,2]
停止条件是len(list)==1时候开始从最底层开始返回
- 注意点
不断生成的是list套list，不能直接将一个数字加上list，比如1+[2,3]≠[1,2,3]，正确的写法是[1]+[2,3]=[1,2,3]，更不要幻想1+[[2,3],[3,2]]=[[1,2,3],[1,3,2]]，正确的做法是利用循环遍历出来进行加法
提取的时候也要注意，这个是有放回式的抽取，剩余应该这样提取rest = nums[:i] + nums[i + 1:]
注意输入本身就是空值
#python3
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
if len(nums) == 1:
return [nums]
res=[]
for i in range(len(nums)):
# res.append(nums[i]+self.permute([nums[i:]]))
prefix = nums[i]
rest = nums[:i] + nums[i + 1:]
for j in self.permute(rest):
res.append([prefix] + j)
return res
sol = Solution()
print(sol.permute([1,2,3]))
- 另一个思路
提炼深度遍历dfs(nums, path, res)
nums是呆遍历的子问题，path是代拼接部分，res是子问题的结果
停止条件是dfs时候nums已空
- 注意
path初始化是空list
class Solution:
# DFS
def permute(self, nums):
res = []
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
# return # backtracking
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
