题解 | #没有重复项数字的全排列#

代码：

public class Solution {
    //我的思路，取出来一个元素，然后剩下的元素去排，排的时候加上取出来那个。
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // if (num.length == 1) {
        //     ArrayList<Integer> list1 = new ArrayList<>(1);
        //     list1.add(num[0]);
        //     ArrayList<ArrayList<Integer>> list2 = new ArrayList<>(1);
        //     list2.add(list1);
        //     return list2;
        // }
        int length = num.length;

        //先把num排序
        Arrays.sort(num);
        //转数组
        List<Integer> sourceList = new ArrayList<>();
        Arrays.stream(num).forEach(v -> sourceList.add(v));

        List<Integer> list = new ArrayList<>(); //依次保存取出来的元素
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();

        // for (Integer i : sourceList) {
        //     list.add(i);
        //     m1(sourceList, i, list, resultList, length);
        // }

        m1(sourceList, null, list, resultList, length);
        return resultList;
    }

    void m1 (List<Integer> sourceList, Integer toRemove, List<Integer> list,
             ArrayList<ArrayList<Integer>> resultList, int length) {
        List<Integer> sourceList2 = new ArrayList<>(sourceList); //深拷贝
        sourceList2.remove(toRemove);
        for (Integer i : sourceList2) {
            ArrayList<Integer> list2 = new ArrayList<>(list); //深拷贝
            list2.add(i);
            if (list2.size() == length) {
                resultList.add(list2);
            } else {
                m1(sourceList2, i, list2, resultList, length);
            }
        }
    }
}

我的做题步骤：

考虑到使用迭代。

我的思路：取出来一个元素，然后剩下的元素去排，排的时候加上取出来那个。然后再取第二个元素，剩下元素去排。

遇到的问题：

1）代码提交后第一个问题出现在深拷贝

这行代码写到了for循环之上，这样会导致第一个元素，一直被放到list中。

2）迭代的初始，不好写初始迭代，用了for循环。

这样也是会导致第一个元素，一直被放到list中。改进，去掉for循环，直接调递归，第一次传入一个null。此时，数组长度等于1的情况也合并到了递归里。

总结：

1）本题，肉眼自测测得不对。

2）迭代的初始步骤，不太会写。我目前的写法是先大概写出来，然后调用递归。后期再看能不能合并到递归里，包括特殊情况也合并到递归里。