Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

BackTracking

回溯法：

1. 修改当前值
2. 递归current node
3. 还原当前值

def permute(self, nums):
 “””
 :type nums: List[int]
 :rtype: List[List[int]]
 “”” 
 
 def backTrack(nums, level):
   if level == len(nums)-1:
     self.ans.append(list(nums))
   return
  for i in range(level, len(nums)):
     nums[level], nums[i] = nums[i], nums[level]
     backTrack(nums, level+1)
     nums[level], nums[i] = nums[i], nums[level]
 self.ans = []
 backTrack(nums, 0)
 return self.ans