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

解法：定好第一位（递归）

每个元素都可以作为第一个元素，当它作为第一个元素时，其他元素进行全排列，再把他们拼起来

而数组不是很好操作，可以先转为列表，这样在删除某个元素的时候不需要移动数组后面的元素

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> allElements = toArrayList(num);
        return permute(allElements);
    }

    private ArrayList<ArrayList<Integer>> permute(ArrayList<Integer>
            elements) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (elements.size() == 0) {
            return result;
        }

        if (elements.size() == 1) {
            ArrayList<Integer> element = new ArrayList<Integer>(elements);
            result.add(element);
            return result;
        }

        for (int index = 0; index < elements.size(); index++) {
            int currentElement = elements.get(index);
            ArrayList<Integer> excludeCurrent = new ArrayList<Integer>(elements);
            excludeCurrent.remove(index);
            ArrayList<ArrayList<Integer>> permuteFromNext = permute(excludeCurrent);
            
            for(int i = 0; i < permuteFromNext.size(); i++){
                ArrayList<Integer> current = new ArrayList<Integer>(elements.size());
                current.add(currentElement);
                current.addAll(permuteFromNext.get(i));
                result.add(current);
            }
        }

        return result;
    }

    private ArrayList<Integer> toArrayList(int[] num) {
        ArrayList<Integer> allElements = new ArrayList<Integer>(num.length);
        for (int i = 0; i < num.length; i++) {
            allElements.add(num[i]);
        }
        return allElements;
    }
}

解法2：选择撤销-递归

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        LinkedList<Integer> resultItem = new LinkedList<Integer>();
        permute(resultItem, num);
        return result;
    }

    private ArrayList<ArrayList<Integer>> permute(LinkedList<Integer>
            resultItem, int[] num) {
        if (resultItem.size() == num.length) {
            result.add(new ArrayList<Integer>(resultItem));
        }

        for (int index = 0; index < num.length; index++) {
            int currentElement = num[index];
            if (resultItem.contains(currentElement)) {
                continue;
            }
            resultItem.add(num[index]);
            permute(resultItem, num);
            resultItem.removeLast();
        }

        return result;
    }


}

注意：在撤销的时候，不要用remove(currentElement),因为元素本身是int类型，会被当成是index；

比如当列表只有两个元素【1， 3】时，如果remove(num[2]), 不会移除元素3，而是移除下标为3的元素，而数组的size是2，因此会产生数组越界

应该使用：

resultItem.remove(resultItem.indexOf(currentElement));

或者：

resultItem.removeLast();