首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Permutations/全排列

[Leetcode][python]Permutations/全排列

作者头像
蛮三刀酱
发布2019-03-26 16:30:45
6270
发布2019-03-26 16:30:45
举报

版权声明:本文为博主原创文章,转载请注明原文地址链接。 https://cloud.tencent.com/developer/article/1407084

题目大意

求一组数的全排列

解题思路

回溯,想起来思路很简单,实际写的时候遇到了很多麻烦。

代码

递归

可能更容易理解,但是代码复杂度高

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = []
        sub = []
        self.dfs(nums,sub)
        return self.res

    def dfs(self, Nums, subList):
        if len(subList) == len(Nums):
            #print res,subList
            self.res.append(subList[:])
        for m in Nums:
            if m in subList:
                continue
            subList.append(m)
            self.dfs(Nums,subList)
            subList.remove(m)

递归方法二

例子:ABC

n = nums[:i] + nums[i+1:]
n = BC
n = A + C = AC
n = AB
最后在ABC+(BC+C)+(AC+A)+(AB+B)
class Solution(object):


    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        print 'nums', nums
        if len(nums) <= 1: 
            return [nums]
        ans = []
        for i, num in enumerate(nums):
            n = nums[:i] + nums[i+1:]  # n是剩余数的list
            print nums[:i], '+', nums[i+1:], '=', n
            for y in self.permute(n):  # 直到函数有return,一个数的时候[nums],所以y是list
                print '递归内:'
                print [num], '+', y, '=',[num] + y
                ans.append([num] + y)
            print '-----End-----'
        return ans

输出:

nums [1, 2, 3]
[] + [2, 3] = [2, 3]
nums [2, 3]
[] + [3] = [3]
nums [3]
递归内:
[2] + [3] = [2, 3]
-----End-----
[2] + [] = [2]
nums [2]
递归内:
[3] + [2] = [3, 2]
-----End-----
递归内:
[1] + [2, 3] = [1, 2, 3]
递归内:
[1] + [3, 2] = [1, 3, 2]
-----End-----
[1] + [3] = [1, 3]
nums [1, 3]
[] + [3] = [3]
nums [3]
递归内:
[1] + [3] = [1, 3]
-----End-----
[1] + [] = [1]
nums [1]
递归内:
[3] + [1] = [3, 1]
-----End-----
递归内:
[2] + [1, 3] = [2, 1, 3]
递归内:
[2] + [3, 1] = [2, 3, 1]
-----End-----
[1, 2] + [] = [1, 2]
nums [1, 2]
[] + [2] = [2]
nums [2]
递归内:
[1] + [2] = [1, 2]
-----End-----
[1] + [] = [1]
nums [1]
递归内:
[2] + [1] = [2, 1]
-----End-----
递归内:
[3] + [1, 2] = [3, 1, 2]
递归内:
[3] + [2, 1] = [3, 2, 1]
-----End-----

答案:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

清爽版:

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        print 'nums', nums
        if len(nums) <= 1: 
            return [nums]
        ans = []
        for i, num in enumerate(nums):
            n = nums[:i] + nums[i+1:]
            for temp_list in self.permute(n):
                ans.append([num] + temp_list)
            print '-----End-----'
        return ans

总结

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年10月03日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
    • 递归
      • 递归方法二
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档