给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1] 输出:[[1]]
示例代码1:
def permute(nums):
ret = []
def backtrace(li, tmp):
if not li:
ret.append(tmp)
return
for i in range(len(li)):
backtrace(li[:i] + li[i + 1:], tmp + [li[i]])
backtrace(nums, [])
return ret
ans = permute([1, 2, 3])
print(ans)
示例代码2:
def permute(nums):
def backtrace(first=0):
# 所有数都填完了
if first == n:
res.append(nums[:])
for i in range(first, n):
# 动态维护数组
nums[first], nums[i] = nums[i], nums[first]
# 继续递归填下一个数
backtrace(first + 1)
# 撤销操作
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
res = []
backtrace()
return res
ans = permute([1, 2, 3])
print(ans)
示例代码3:
class Solution(object):
def permute(self, nums):
n = len(nums)
res, path, tmp = [], [], [False] * n
def traceback():
if len(path) == n:
res.append(path[:])
return
for i in range(n):
if tmp[i]:
continue
path.append(nums[i])
tmp[i] = True
traceback()
path.pop()
tmp[i] = False
traceback()
return res
nums = [1, 2, 3]
obj = Solution()
ret = obj.permute(nums)
print(ret)
示例代码4:
class Solution(object):
def permute(self, nums):
n = len(nums)
ret, path = [], []
def backtrace():
if len(path) == n:
ret.append(path[:])
return
for i in range(n):
if nums[i] in path:
continue
path.append(nums[i])
backtrace()
path.pop()
backtrace()
return ret
nums = [1, 2, 3]
obj = Solution()
ret = obj.permute(nums)
print(ret)