力扣46. 全排列

46. 全排列

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

示例:

输入: [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个元素的排列，

1. 当k == 1时，只有一个元素，已构成一个排列

2. 对任意的k, 1<k <= n，如果可由该函数完成数组后面 k - 1个元素的排列，为完成后面k个元素的排列，逐一对第 n - k个元素与数组中第 n - k ~ n元素进行交换，每互换一次，就执行一次perm(nums, k - 1, rsult)函数,产生一个排列。

 1 class Solution {
 2     public List<List<Integer>> permute(int[] nums) {
 3 
 4         ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
 5         perm(nums, nums.length, result);
 6         return result;
 7     }
 8 
 9     public void swap(int[] nums, int a, int b){
10         int temp = nums[a];
11         nums[a] = nums[b];
12         nums[b] = temp;
13     }
14 
15     public void perm(int[] nums, int k,  ArrayList<List<Integer>> result){
16         // 如果k == 1，说明只有一个元素，已构成一个排列
17         int n = nums.length;
18         if(k == 1){
19             List<Integer> list = new ArrayList<Integer>();
20             for(int i = 0; i < n; i++){
21                 list.add(nums[i]);
22             }
23             result.add(list);
24         }
25         for(int i = n - k; i < n; i++){
26             // 让n - k这个元素和每个元素都交换一次
27             swap(nums, n - k, i);
28             // 生成一个 k - 1的排列
29             perm(nums, k - 1, result);
30             // 换回来
31             swap(nums, n - k, i);
32         }
33     }    
34 }

复杂度分析：

时间复杂度为：根据递归方程 f(1) = n; f(n) = n * f(n-1) (n>1), 求得f(n) = n*n!, 所以算法的时间复杂度为O(nn!)

空间复杂度，最多递归n层，所以空间复杂度为O(n)