[Leetcode][python]Permutations/全排列

末蓝、 2022-06-07 01:22 164阅读 0赞

## 题目大意 ##

求一组数的全排列

## 解题思路 ##

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

## 代码 ##

### 递归 ###

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

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

## 总结 ##