给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
定义符号N=nums的长度。
要想给出长度为k的所有全排列Ak，只需要有所有长度为k-1的全排列Ak-1。然后从将Ak-1和N-k个没有使用过的数字中的每一个进行连接，即可得到所有的Ak。对于“没有使用”这个概念，专门设置一个布尔类型数组used，来记录每一个数字是否已经被使用。
这明显是一个递归的思路。当递归开始的时候，A0=空字符串。当递归结束的时候k=N，因此将k=N作为递归终止条件。
题目要求返回的是所有全排列，而非其个数。因此在递归的时候还需要维护一个list，在每一次递归的时候加入本次连接的数字。
综上，递归传入的参数是长度k，以及上一层递归得到的list。
代码：
class Solution: def permute(self, nums): self.nums = nums self.res_list = [] # 记录结果 self.N = len(nums) self.used = [False for i in range(self.N)] # 记录已经使用过的数字 self.dc(0, []) return self.res_list def dc(self, occupy, current): if self.N == occupy: # 递归终止条件 self.res_list.append(current) return for i in range(self.N): if not self.used[i]: # 表示第i个元素是可用的 # 将第i个元素设置为不可用，进入递归 self.used[i] = True self.dc(occupy+1, current+[self.nums[i]]) # 结束递归后将第i个元素设置为可用 self.used[i] = False s = Solution() print(s.permute([1,2,3,-1]))