题意

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

示例:

输入: [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