46. 全排列

46. 全排列

题意

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

示例:

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

解题思路

1. 回溯：遍历数组，两两交换给定对应下标的值；

2. 记忆化：通过遍历当前路径数组，遍历当前的路径数组选择位置来插入index对应的值实现；

实现

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
            
        def helper(index):
            if index >= len(nums):
                res.append(nums[:])
                return
            for i in range(index, len(nums)):
                swap(i, index)
                helper(index+1)
                swap(index, i)
        
        res = []
        helper(0)
        return res
      
  def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def helper(index, path):
            if len(path) == len(nums):
                res.append(path[:])
            else:
               # 长度+1是为了考虑当path为空的情况下能够进入循环
                # 同时也考虑到需要插入到path下标的位置
                for i in range(0, len(path) + 1):
                   # i代表插入的位置，将index对应的值插入到path中
                    helper(index + 1, path[:i] + [nums[index]] + path[i:])
​
        res = []
        helper(0, [])
        return res
      
  def permute(self, nums):
       "和上面一样的思路，迭代实现，遍历当前数组，选择插入位置"
        if not nums:
            return []
        res = [[]]
​
        # 选定一个元素
        for num in nums:
            # 遍历结果，加入这个元素
            temp = []
            for cur in res:
                # 选择插入位置
                for i in range(len(cur)+1):
                    temp.append(cur[:i] + [num] + cur[i:])
            res = temp
        return res