Skip to content

046 permutations

46. Permutations

题目: https://leetcode.com/problems/permutations/

难度:

Medium

每次取一个作为prefix, 剩下的继续做permutation,然后连接起来加入res中

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        res = []
        for i in range(len(nums)):
            prefix = nums[i]
            rest = nums[:i] + nums[i+1:]
            for j in self.permute(rest):
                res.append([prefix]+j)
        return res

还有介绍的基本无memory使用的算法:

class Solution:
    def permute(self, num):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(num) == 0: yield []
        if len(num) == 1: yield [num]
        res = []
        for i in range(len(num)):
            x  = num[i]
            xs = num[:i] + num[i+1:]             
            for j in self.permute(xs):
                res.append([x] + j)
        yield res

但是这个yield只是生产generator,要看结果还是要用for in 来查看res的。



回到顶部