题目描述(题目难度，中等)
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣(LeetCode)
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目求解
全排列一般都用递归求解，不仅限于以下两种解法，但解法一已经达到效率最大化，解法二为最常见的解法，所以了解这两种解法就足够了。
解法一
class Solution {
public List> permute(int[] nums) {
List> result = new ArrayList();
permutation(result, nums, 0);
return result;
}
private void permutation(List> result, int[] nums, int li){
ArrayList list = new ArrayList();
for(int e : nums) list.add(e);
result.add(list);
// 从li开始顺序两两交换
for(int i = li; i < nums.length; ++i) {
for(int j = i+1; j < nums.length; ++j) {
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
permutation(result, nums, i+1);
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}
}
}
下面这个代码和上面的思路完全一样，但效率会有所提高。
class Solution {
public List> permute(int[] nums) {
List> result = new LinkedList();
List numsList = new ArrayList();
for(int e : nums) numsList.add(e);
permutation(result, numsList, 0);
return result;
}
private void permutation(List> result, List nums, int li){
result.add(new ArrayList(nums)); // 效率主要提高在这，native 拷贝方法会比写 for 循环拷贝要快
// 从li开始顺序两两交换
for(int i = li; i < nums.size(); ++i) {
for(int j = i+1; j < nums.size(); ++j) {
Collections.swap(nums, i, j);
permutation(result, nums, i+1);
Collections.swap(nums, i, j);
}
}
}
}
解法二
全排列更常见的解法：
class Solution {
public List> permute(int[] nums) {
List> result = new ArrayList();
List numsList = new ArrayList();
for(int e : nums) numsList.add(e);
permutation(result, numsList, 0);
return result;
}
private void permutation(List> result, List nums, int li){
if(li == nums.size()-1) result.add(new ArrayList(nums));
for(int i = li; i < nums.size(); ++i) {
Collections.swap(nums, li, i);
permutation(result, nums, li+1);
Collections.swap(nums, i, li);
}
}
}
效率对比
解法一的效率要比解法二高，因为解法一每次调用递归函数都会生成一个结果序列，使用递归树表示，其节点数目为
；解法二使用递归树表示，只会在叶子节点生成结果序列，所以会有
个叶子节点。所以解法一递归树的规模要远远小于解法二。
解法一的递归树如下所示：
递归树1.png
其中 P 表示递归函数，括号中的参数表示参数 li，椭圆表示节点，矩形左下角的值表示框住节点的个数。
有点复杂，举个具体的例子，以 n=4 为例，我们来看一下递归函数的调用次数是否为 ：
n=4递归树1的情况.png
第一层的节点数：
第二层的节点数：
第三层的节点数：
第四层的节点数：
所以总的节点数为：
不知道这个递归树是否隐藏着一个
的表达式，数学水平有限，未去深究。
解法二的递归树如下：
递归树2