【递归 &回溯】Leecode-46. 全排列
【摘要】 【题目】给定一个不含重复数字的数组 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...
【题目】
给定一个不含重复数字的数组 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:
- 思路
列出可能的树形图,对于给出的列表逐个遍历调用dfs
- 复杂度
时间复杂度:O(n2),空间复杂度:O(n)
- 代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrace(first):
if first == size:
res.append(nums[:])
return
for i in range(first, size):
nums[first], nums[i] = nums[i], nums[first]
backtrace(first+1)
nums[first], nums[i] = nums[i], nums[first]
size = len(nums)
res = []
backtrace(0)
return res
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)