【递归 &回溯】Leecode-46. 全排列

举报
子都爱学习 发表于 2024/01/03 19:53:55 2024/01/03
【摘要】 【题目】给定一个不含重复数字的数组 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。