全排列算法

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

算法如下：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> target = new ArrayList<>();
        for (int num:nums){
            target.add(num);
        }
        trance(ret,0,nums.length,target);
        return ret;
    }
    public void trance(List<List<Integer>> ret,int cursor,int length,List<Integer> target){
        if(cursor == length-1){
            //这里要注意：要重新实例化一个ArrayList，因为target是一个引用地址
            ret.add(new ArrayList<Integer>(target));
            return;
        }
        //这里的思想很重要，以cursor下标为点，依次和cursor后面的下标交换，这样就会得出cursor下标不同值的n个数组，
        //cursor下标排完之后，在以cursor+1下标为准，一次进行上述操作，当cursor为length-1时则全部遍历完了，依次
        //添加进数组即可。
        for (int i = cursor;i<length;i++){
            Collections.swap(target,cursor,i);
            trance(ret,cursor+1,length,target);
            Collections.swap(target,cursor,i);
        }
    }
}

这个算法有俩个疑问点：

• 为什么cursor == length-1时才需要添加add呢？看下图的递归树就明白了

• 为什么 Collections.swap(target,cursor,i)之后还需要 Collections.swap(target,cursor,i)呢？
  举个例子，原数组1，2，3 当游标为0时的意思是后面的元素2和3都和1元素置换。
  当第一次置换之后为2 ，1，3，此时我们需要将2，1，3还原成1，2，3之后才能继续和3置换成3，2，1，如果不还原成1，2，3直接置换之后的结果为3，1，2了