目錄
1、LeetCode46:給定一個 沒有重複 數位的序列,返回其所有可能的全排列。
2、LeetCode47:給定一個可包含重複數位的序列,返回所有不重複的全排列。
1、LeetCode46:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
2、LeetCode47:
輸入: [1,1,2] 輸出: [ [1,1,2], [1,2,1], [2,1,1] ]
1、LeetCode46:遞迴+回溯
2、LeetCode47:遞迴+回溯+去重
1、LeetCode46:
class Solution:
def permute(self, nums: int):
res = []
def DFS(nums, tmp):
if nums == []:
res.append(tmp)
return
for i in range(len(nums)):
DFS(nums[:i] + nums[i + 1:], tmp + [nums[i]])
DFS(nums, [])
return res
if __name__ == '__main__':
test = [1,2,3]
ans = [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
s = Solution()
res = s.permute(test)
print('test:', test)
print('ans:', ans)
print('res:', res)
2、LeetCode47:(該程式碼也可用於LeetCode46)
class Solution:
def permuteUnique(self, nums):
res = []
nums.sort()
def DFS(num, tmp):
if num == []:
res.append(tmp)
return
for i in range(len(num)):
if i > 0 and num[i - 1] == num[i]:
continue
DFS(num[: i] + num[i + 1: ], tmp + [num[i]])
DFS(nums, [])
return res
if __name__ == '__main__':
test = [1,1,2]
ans = [
[1,1,2],
[1,2,1],
[2,1,1]
]
s = Solution()
res = s.permuteUnique(test)
print('test:', test)
print('ans:', ans)
print('res:', res)