首页 > 其他 > 详细

46全排列

时间:2019-11-27 14:17:35      阅读:61      评论:0      收藏:0      [点我收藏+]

题目: 给定一个没有重复数字的序列,返回其所有可能的全排列。

示例: 输入: [1,2,3]输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

来源: https://leetcode-cn.com/problems/permutations/

法一: 自己的代码

思路: 很基本的回溯算法,没有剪枝条件,r中每次传递的都是去掉已经用过的数,

技术分享图片
class Solution:
    def permute(self, nums):
        resluts = []
        l = len(nums)
        # 注意这里的nums如果不初始化的话,要放在a的前边,否则报错.
        def backtrack(a=[], nums=nums):
            # 深度优先遍历,即回溯终止的条件
            if len(a) == l:
                resluts.append(a)
            for j,i in enumerate(nums):
                # 每次回溯前,都将该数删除,为了下次回溯for循环的时候不再用
                # 这里没有用状态重置是因为 回溯时用了r来赋值给nums,每次回溯结束后仍然是原来的状态
                r = nums.copy()
                del r[j]
                # 这里的i必须加[]
                backtrack( a+[i], r)
                # 也可以不用引入r直接生成list传递,耗时稍微短点
                # backtrack( a+[i], [k for k in nums if k != i])
        backtrack()
        return resluts
if __name__ == "__main__":
    duixiang = Solution()
    a = duixiang.permute([1,2,3])
    print(a)
View Code

法二:

 

 

 

46全排列

原文:https://www.cnblogs.com/xxswkl/p/11941786.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!