leetcode 46. 全排列（Java版）

题目描述（题目难度，中等）

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

示例:

输入: [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<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        permutation(result, nums, 0);
        return result;
    }
    private void permutation(List<List<Integer>> result, int[] nums, int li){
        ArrayList<Integer> 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<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList();
        List<Integer> numsList = new ArrayList();
        for(int e : nums) numsList.add(e);
        permutation(result, numsList, 0);
        return result;
    }
    private void permutation(List<List<Integer>> result, List<Integer> 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<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        List<Integer> numsList = new ArrayList();
        for(int e : nums) numsList.add(e);
        permutation(result, numsList, 0);
        return result;
    }
    private void permutation(List<List<Integer>> result, List<Integer> 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