import copy
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
if nums is None:
return []
if nums == []:
return [[]]
nums.sort()
results = list()
self.dfs(0, nums, results)
return results
def dfs(self, index, nums, results):
# 搜索到结尾， 输出一个结果
if index == len(nums):
results.append(copy.copy(nums))
return
i = index
#print(i, nums)
marked = set()
while i < len(nums):
if nums[i] not in marked:
marked.add(nums[i])
self.switch(index, i, nums)
print(index, i, nums, marked)
# 排列这里是 index + 1 而不是 i + 1. 不然会出现漏掉的情况。组合的话是 i + 1.见 subset
self.dfs(index+1, nums, results)
self.switch(i, index, nums)
i += 1
def switch(self, i, j, array):
array[i], array[j] = array[j], array[i]
