046._permutations.md

###46. Permutations

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

难度:

Medium

复习了一下,自己写的容易理解版本：

每次调一个放入现有

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

    def recPermute(self, sofar, rest):
      if rest == []:
        self.result.append(sofar)
      else:
        for i in range(len(rest)):
          next = sofar + [rest[i]]
          remaining = rest[:i] + rest[i+1:]
          self.recPermute(next, remaining)

交换

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.helper(nums,0,result)
        return result
    
    def helper(self,nums,begin,result):
        n = len(nums)
        if begin == n:
            tmp = nums[:]
            result.append(tmp)
            return
        
        for i in range(begin,n):
            nums[begin], nums[i] = nums[i],nums[begin]
            self.helper(nums,begin+1,result)
            nums[begin],nums[i] = nums[i],nums[begin]
     

好像还有一个巧妙的版本

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permute(self, num):
        if len(num) == 0: return []
        if len(num) == 1: return [num]
        res = []
        for i in range(len(num)):
            for j in self.permute(num[:i] + num[i+1:]):
                res.append([num[i]] + j)
        return res

更容易理解的写法：

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permute(self, num):
        if len(num) == 0: return []
        if len(num) == 1: return [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)
        return res

就是一定要有递归的信念❤️

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

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permute(self, num):
        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的。