给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
思路：
假定算法perm(int[] nums, int k, ArrayList<List<Integer>> result)表示对n个元素的数组nums生成后面k个元素的排列，
已知 perm(int[] nums, int k, ArrayList<List<Integer>> result)函数可以生成数组中第k到第n个元素的全排列，如果我们让第k位元素和每一个元素进行交换，这样第k个位置就曾经被被每个元素都占有过，接下来使用递归生成数组从第k+1位到第n位的全排列，这样第k个元素的全排列加上后(n-k-1)个元素的全排列就是整个数组的全排列。该数组第k+1个元素到第n 个元素的全排列又会等于第k+1个元素和后面每个元素进行交换的全排列加上后面(n-k-2)个元素的重排列。
1. 当k == n-1时，只有一个元素，已构成一个排列
2. 对任意的k, 1<k <= n， 如果可由该函数完成数组后面 k - 1个元素的排列，为完成后面k个元素的排列，逐一对第 k个元素与数组中第 n - k-1元素进行交换，每互换一次，就执行一次perm(nums, k + 1, rsult)函数,产生一个排列。
1 class Solution { 2 public List > permute(int[] nums) { 3 List > res = new ArrayList >(); 4 helpPermutation(nums, 0, res); 5 return res; 6 } 7 8 public void swap(int[] nums, int i, int j){ 9 int temp = nums[i];10 nums[i] = nums[j];11 nums[j] = temp;12 }13 14 public void helpPermutation(int[] nums, int k, List > res){15 int n = nums.length;16 // 如果是第n-1个元素的重排列，说明只有一个元素了，说明当前数组已经产生了一个新的全排列17 // 可以把当前数组保存下来了18 if(k >= n-1){ 19 ArrayList temp = new ArrayList ();20 for(int i = 0; i < n; i++){21 temp.add(nums[i]);22 }23 res.add(temp);24 return;25 }26 27 // 说明当前需要排列的数组长度还不为1，继续和后面的元素进行交换后递归28 for(int i = k; i < n; i++){29 swap(nums, k, i); // 第k位元素和后面每个元素进行交换30 helpPermutation(nums, k+1, res); // 第k+1位及之后的数组全排列使用递归生成31 // 生成已第i个元素为第k位的全排列后要把k, i的元素换回来，32 // 因为因为下一步要让第k个元素和第i+1个元素进行交换33 swap(nums, k, i); 34 }35 }36 }
leetcode 执行用时：0 ms > 100.00%, 内存消耗：39.1 MB > 42.62%
复杂度分析：
时间复杂度为：根据递归方程 f(1) = 1; f(n) = n * f(n-1) (n>1), 求得f(n) = n!, ， 另外每次产生一个全排列序列，都需要花费一个O(n)的时间把这个排列拷贝到结果集中，所以算法的时间复杂度为O(nn!)
空间复杂度：最多递归n层，所以空间复杂度为O(n)
稍加变动的写法
可以考虑在主函数中把nums数组拷贝到一个集合中，这样可以省去每次都对nums数组进行遍历，把所有元素都拷贝到一个temp集合中，省去一个循环，但是复杂度没有降低，因为底层拷贝列表还是有一个循环
1 class Solution { 2 public List > permute(int[] nums) { 3 List > res = new ArrayList >(); 4 ArrayList inputNums = new ArrayList<>(); 5 for(int num : nums){ 6 inputNums.add(num); // 把数组拷贝到一个集合中，可以省去一些时间 7 } 8 helpPermutation(inputNums, 0, res); 9 return res;10 }11 12 public void helpPermutation(ArrayList inputNums, int k, List > res){13 int n = inputNums.size();14 // 如果是第n-1个元素的重排列，说明只有一个元素了，说明当前数组已经产生了一个新的全排列15 // 可以把当前数组保存下来了16 if(k >= n-1){ 17 res.add(new ArrayList (inputNums));18 return;19 }20 21 // 说明当前需要排列的数组长度还不为1，继续和后面的元素进行交换后递归22 for(int i = k; i < n; i++){23 Collections.swap(inputNums, k, i); // 第k位元素和后面每个元素进行交换24 helpPermutation(inputNums, k+1, res); // 第k+1位及之后的数组全排列使用递归生成25 // 生成已第i个元素为第k位的全排列后要把k, i的元素换回来，26 // 因为因为下一步要让第k个元素和第i+1个元素进行交换27 Collections.swap(inputNums, k, i); 28 }29 }30 }
leetcode 执行用时：0 ms > 100.00%, 内存消耗：39.1 MB > 42.62%
复杂度分析：
时间复杂度为：根据递归方程 f(1) = 1; f(n) = n * f(n-1) (n>1), 求得f(n) = n!, ， 另外每次产生一个全排列序列，都需要花费一个O(n)的时间把这个排列拷贝到结果集中，所以算法的时间复杂度为O(nn!)
空间复杂度：最多递归n层，所以空间复杂度为O(n)
改成下面这种形式，按理来说应该效率是一样的，但是根据leetcode运行时间来看，比上面两种慢了一些
1 class Solution { 2 public List > permute(int[] nums) { 3 List > res = new ArrayList >(); 4 helpPermutation(nums, 0, new LinkedList (), res); 5 return res; 6 } 7 8 public void swap(int[] nums, int i, int j){ 9 int temp = nums[i];10 nums[i] = nums[j];11 nums[j] = temp;12 }13 14 public void helpPermutation(int[] nums, int k, LinkedList temp, List > res){15 int n = nums.length;16 // 如果是第n个元素的重排列，说明当前数组已经产生了一个新的全排列17 // 可以把当前数组保存下来了18 if(k >= n){ 19 res.add(new LinkedList (temp));20 return;21 }22 23 // 说明当前需要排列的数组长度还不为1，继续和后面的元素进行交换后递归24 for(int i = k; i < n; i++){25 temp.addLast(nums[i]);26 swap(nums, k, i); // 第k位元素和后面每个元素进行交换27 helpPermutation(nums, k+1, temp, res); // 第k+1位及之后的数组全排列使用递归生成28 // 生成已第i个元素为第k位的全排列后要把k, i的元素换回来，29 // 因为因为下一步要让第k个元素和第i+1个元素进行交换30 swap(nums, k, i);31 temp.removeLast(); 32 }33 }34 }