15 Permutation
Given a list of numbers, return all possible permutations.
Example
For nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Code
class Solution:
"""
@param: nums: A list of integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
result = []
self.dfs(nums, [], result)
return result
def dfs(self, nums, res, reslist):
if len(res) == len(nums): #终止条件，一次全排列完成
reslist.append(res)
return
for i in range(len(nums)):
if nums[i] not in res:
self.dfs(nums, res+[nums[i]], reslist)
#最后输出需要把单个list按len(nums)重新组合一下
16 permutation 2
Given a list of numbers with duplicate number in it. Find all unique permutations.
Example
For numbers [1,2,2] the unique permutations are:
[
[1,2,2],
[2,1,2],
[2,2,1]
]
Idea
与15题非常相似，只是会出现重复元素 所以还是使用next_permutation来做，也还是需要先排序保证所有排列出现 但是需要增加一个lastv来判断这个新的vector是否与上一个相同，不相同的情况下才将其保存
Code
class Solution:
"""
@param: : A list of integers
@return: A list of unique permutations
"""
def permuteUnique(self, nums):
# write your code here
if len(nums) == 0:
return [[]]
res = []
nums.sort()
visited = [[False] for i in range(len(nums))]
self.dfs(nums, [], res, visited)
return res
def dfs(self, nums, subset, result, visited):
if len(nums) == len(subset):
result.append(subset[:])
for i in range(len(nums)):
if visited[i] ==True:
continue
if i-1>=0 and visited[i-1] ==True and nums[i-1] == nums[i]:
continue
visited[i] = True
subset.append(nums[i])
self.dfs(nums, subset, result, visited)
visited[i] = False
subset.pop()
