首页 > 代码库 > LeetCode 46. Permutations
LeetCode 46. Permutations
原题
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3]have the following permutations:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解题思路
递归：递归的方法，创建一个visit判断此值是否已经添加过，每一层不断地循环，加入没有被访问的元素，直到最后结果的长度满足要求加入答案中
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if nums == None:
return []
visit = [0 for i in range(len(nums))]
self.ret = []
self._permute(nums, visit, 0, [])
return self.ret
def _permute(self, nums, visit, count, ret):
if count == len(nums):
self.ret.append(ret)
return
for i in xrange(len(nums)):
if visit[i] == 0:
# ret += [nums[i]] 容易出错，如果加入这句后面需要还原，不然影响后面的循环
visit[i] = 1
self._permute(nums, visit, count+1, ret+[nums[i]])
visit[i] = 0
非递归：跟之前求subsets的思路类似（不过这个是求重复项，sbusets是求非重复），也是从一个个元素一层层加上去，只不过加入结果的时候必须满足长度要求
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if nums is None:
return []
result = []
self.helper(nums, [], result)
return result
def helper(self, List, path, result):
if len(path) == len(List):
result.append(path)
return
# 跟subsets思路差不多，不过这个是重复，sbusets是非重复
# 也是从一个个元素一层层加上去，只不过加入结果的时候必须满足长度要求
for i in range(len(List)):
# 不重复加入同一元素
if List[i] in path:
continue
# path.append(List[i])
self.helper(List, path + [List[i]], result)
# path.pop()
LeetCode 46. Permutations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。