給出一串不重復(fù)的數(shù)，輸出所有排列數(shù)
思路一：DFS+保存路徑
寫法一
1 #46
2 #Runtime: 56 ms
3 #Memory Usage: 13.4 MB
4
5 class Solution(object):
6
7 def permute(self, nums):
8 """
9 :type nums: List[int]
10 :rtype: List[List[int]]
11 """
12 vis = [0] * len(nums)
13 self.res = []
14 self.dfs(nums, vis, [])
15 return self.res
16
17 def dfs(self, nums, vis, s):
18 if len(s) == len(nums):
19 self.res.append(list(s))
20 return
21 else:
22 for i in range(len(nums)):
23 if vis[i] == 0:
24 vis[i] = 1
25 s.append(nums[i])
26 self.dfs(nums, vis, s)
27 s.pop()
28 vis[i] = 0
寫法二（更快更短）
1 #46
2 #Runtime: 16 ms (Beats 95.78%)
3 #Memory: 13.5 MB (Beats 34.30%)
4
5 class Solution(object):
6
7 def permute(self, nums):
8 """
9 :type nums: List[int]
10 :rtype: List[List[int]]
11 """
12 self.ans = []
13 self.vis = [0] * len(nums)
14 def dfs(t, k):
15 if k == len(nums):
16 self.ans.append(t[:])
17 return
18 for i in range(len(nums)):
19 if not self.vis[i]:
20 t.append(nums[i])
21 self.vis[i] = 1
22 dfs(t, k + 1)
23 self.vis[i] = 0
24 t.pop()
25 dfs([], 0)
26 return self.ans
思路二：Python的生成排列的函數(shù)
1 #46
2 #Runtime: 20 ms
3 #Memory Usage: 13.7 MB
4
5 class Solution(object):
6 def permute(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[List[int]]
10 """
11 return permutations(nums)