博客

全排列是一个很经典的用递归算法解决的题目，也是先说明一下对题目的理解。

1的全排列是[1]

1,2的全排列是[1,2][2,1]

1,2,3的全排列的[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]

我们可以看出：

1的全排列只有1个

1，2的全排列有2*1个

1,2，3的全排列有3 * 2 * 1个

所以，n个数字的全排列的个数为n！个

我们以1,2,3这种序列举例来看，他的六组全排列的序列是如何得到的呢，也就会成为我们实现这个题逻辑的关键：

1. 我们可以把1 2 3的全排列看成2 3的全排列的结果插入1的不同情况的列举。
2. 当我们把1 2 3传入计算全排列的方法里之后，可以先不看1，先去排2 3
3. 也就是说，先swap出来1 2 3 ， 1 3 2，add进我们的list里
4. 然后交换之后，再用相同递归的层数，让数组还原成为原来的顺序，以方便我们从23的swap转换为123的swap。
5. 然后，直到我们将整个数组遍历完成，就结束。

注意，让递归结束的条件，我们可以直接设置成为，超过nums.length，然后让swap (2,3)的时候(我们肯定也得遍历到1，是有这个过程的)，对于1在遍历的时候，我们可以swap(1,1)，也就是自己和自己交换，这样就没问题了。

以下是我的代码实现：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list1 = new ArrayList<>();
        dfs(list1,nums,0);
        return list1;
    }
    
    //往目的串中添加list
    public void dfs(List<List<Integer>> list1,int []nums,int i){
        
        if(i == nums.length){
            List<Integer> list = new ArrayList<>();
            for(int k : nums) list.add(k);
            list1.add(list);
        }
        
        for(int j = i;j<nums.length;j++){
            swap(nums,j,i);
            dfs(list1,nums,i+1);
            swap(nums,j,i);
        }
    }
    //交换
    public void swap(int []nums,int i , int j){
        int term = nums[i];
        nums[i]=nums[j];
        nums[j]=term;
    }
}