#题目： 这里主要考虑的是无重复的全排列
比如： (1,2,3) 全排列为 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

#method 1 /*

    public ArrayList<ArrayList<Integer>> Permutation(int[] nums){
        ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        helper(nums,0,arr,arrs);
        return arrs;
    }
    /*
     * 简单地说：就是第一个数分别以后面的数进行交换
     *E．g：E = （a , b , c），则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（a,b）
     *然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行
     */
    
    public void helper(int[] nums,int pos,ArrayList<Integer> arr,ArrayList<ArrayList<Integer>> arrs){
        if(pos == nums.length){
            //这是正确的写法

            arr = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                arr.add(nums[i]);
            }
            arrs.add(arr);
            
            //差一点点  天壤之别系列1  不正确

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

//              arr.add(nums[i]);

//          }

//          arrs.add(arr);

            
            //差一点点  天壤之别系列2    不正确

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

//              arr.add(nums[i]);

//          }

//          arrs.add(new ArrayList<>(arr));

        }else{
            /**
             * 我觉得过程是这样的
             * perm(a,b,c) = a+perm(b,c)(pos = 0 取出a) = 
             */
            for (int i = pos; i < nums.length; i++) {    //pos表示

                swap(nums,i,pos); //pos表示当前数       

                helper(nums,pos+1,arr,arrs);    //当前pos位置确定，在pos位置后面继续全排列

                swap(nums,i,pos);     //还原到原来的数组

            }
        }

#method 2 采用迭代的方法真是感觉想出这个方法的人 牛逼
//再提供一个更为巧妙的全排列思路
/* * 第 1 步：
当只有1个数字1的时候，只有一种组合
1
第 2 步：
当有两个数字1、2的时候，分别把 2 放到 1 的前面和后面，就可以得到下面两个组合
2 1
1 2
第 3 步.
当有三个数字1、2、3的时候，可以针对第 2 步中得到的两个组合，把 3 分别插入这两个组合之中。
对于组合 2 1，我们可以得到下面 3 个组合：
3 2 1
2 3 1
2 1 3
对于组合 1 2，我们可以得到下面 3 个组合：
3 1 2
1 3 2
1 2 3
于是我们一共得到了 6 个组合
第 4 步：
对于四个数字1、2、3、4，按照第 3 步中的做法，将 4 分别插入在第 3 步中得到的 6 个组合，最后我们可以得到 24 个组合
可用循环表示，真是方便极了
*/

    public ArrayList<ArrayList<Integer>> PermutationByRecursion(int[] nums){
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if(nums.length<=0){
            return lists;
        }
        ArrayList<Integer> list = new ArrayList<>();
        if(nums.length>0){
            list.add(nums[0]);
            lists.add(list);
        }
        
        for (int i = 1; i < nums.length; i++) {    //表示每次取得是第几个数

            int lastSize = lists.size();     //这里避免死循环   取出上一次集合的大小

            for (int j = 0; j < lastSize; j++) {    //遍历上一次集合中有多少排列   

                for (int j2 = 0; j2 < lists.get(0).size()+1; j2++) {    //取出第一个排列，依次插入新的数，组成新的排列    插入的话可以插入多一个位置

                    ArrayList<Integer> arr = new ArrayList<>(lists.get(0));
                    arr.add(j2, nums[i]);
                    lists.add(arr);
                }
                lists.remove(0);    //始终移除第一个排列

            }
        }
        return lists;
    }