LeetCode46-全排列(递归)

递归的使用，是真的烧脑子，只能多练。

整个思路就是，对每个数，进行匹配。

每次把1个数加到自己后面，再和剩下的全排列

这道题！是没有重复数字的！这非常好做！

举个例子

1，2，3，4吧

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　【1】

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　【1、2】　　【1、3】　　【1、4】

　　　　　　　　　　　　　　　　　　　　　【1、2、3】　　【1、2、4】　　【1、3、2】　　【1、3、4】　　【1、4、3】　　【1、4、2】

　　　　　　　　　　　　　　　　【1、2、3、4】　　【1、2、4、3】　　【1、3、2、4】　　【1、3、4、2】　　【1、4、3、2】　　【1、4、2、3】

但对于2也是这样

总的来说，就是拿上一次的结果，加上自己后，进行递归。

递归就是循环选择数组里面还没在list里面的元素，加在后面。

这个代码很难写，多品一品

有个小技巧，不一定非得拿返回值，把结果存在参数里也行。这样直观一点，像全局变量一样，拿返回值很复杂

public class LeetCode46 {

    public static void main(String[] args) {

        int [] a = {1,2,3};

        List<List<Integer>> res = permute(a);

        for(int i=0;i<res.size();i++){
            List<Integer> list = res.get(i);
            for(int j=0;j<list.size();j++){
                System.out.print(list.get(j));
            }
            System.out.println();
        }


    }
    
    public static List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();

        for(int i=0;i<nums.length;i++){
            List<Integer> temp = new ArrayList<>();
            //对每个元素进行递归
            temp.add(nums[i]);
            digui(nums,temp,res);
        }

        return res;
    }


    //其实是每次对list和剩下的元素进行全排列
　　//list是上一次的结果

    public static void digui(int nums[],List<Integer> list,List<List<Integer>> res){

        //最后的递归，在这里收集数据，上一次的结果list长度和数组一样长了，就是说一次排列完成
        if(list.size()==nums.length){
            res.add(list);
            return;
        }

        for(int i=0;i<nums.length;i++){

            //如果这个数字前面没出现过的话，那么就加入当前数组中，进行下一次全排列
            if(!list.contains(nums[i])){
                List<Integer> temp = new ArrayList<>();
                for(int j=0;j<list.size();j++){
                    temp.add(list.get(j));
                }
                temp.add(nums[i]);
                digui(nums,temp,res);
            }

        }

        //循环跑完了就退出了

    }

}