//递归方法

    public List<List<Integer>> permute2(int[] num) {

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

        permute(num, 0, result);

        return result;

    }

    void permute(int[] num, int start, List<List<Integer>> result) {

        if (start == num.length)

        {

            ArrayList<Integer> item = convertArrayToList(num);

            //List<int[]> list = Arrays.asList(num);这个方法适合String，而不适合int，会把int[]当成一个元素加入list

            result.add(item);

        }

        for (int j = start; j < num.length; j++)

        {

            //递归方法，首先1和1交换，求除nums[1]外的序列的全排列，然后1和1再交换回来。1和2交换，求除了nums[1]之外的序列的全排列，然后1和2再交换回来。

            swap(num, start, j);

            permute(num, start + 1, result);

            swap(num, start, j);

        }

    }

    private ArrayList<Integer> convertArrayToList(int[] num) {

        ArrayList<Integer> item = new ArrayList<Integer>();

        for (int h = 0; h < num.length; h++) {

            item.add(num[h]);

        }

        return item;

    }

    private void swap(int[] a, int i, int j) {

        int temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

public List<List<Integer>> permute(int[] num) {

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

        //start from an empty list

        result.add(new ArrayList<Integer>());

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

        {

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

            for (List<Integer> l : result)

            {

                //插入size+1个位置

                for (int j = 0; j < l.size()+1; j++)

                {

                    l.add(j, num[i]);

                    ArrayList<Integer> temp = new ArrayList<Integer>(l);

                    current.add(temp);

                    l.remove(j);

                }

            }

            result = new ArrayList<>(current);

        }

        return result;

    }