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

方法：递归+回溯

因为有重复的元素，所以需要去重，前面用到的交换的方法不适用了。这里我们采用一个临时数组记录当前添加的结果，用一个标记数组判断哪些元素已经加入，再每次添加时都需要判断是否和前一个元素相等，相等则不添加。

步骤：

• step 1：先对数组按照字典序排序，获取第一个排列情况。
• step 2：准备一个数组暂存递归过程中组装的排列情况。使用额外的visited数组用于记录哪些位置的数字被加入了。
• step 3：每次递归先判断，若临时数组长度到达原数组长度就是一种排列情况。
• step 4：从头遍历数组，获取数字加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用，也不需要将其纳入。
• step 5：进入下一层递归前将vis数组当前位置标记为使用过。
• step 6：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入数组的元素。

import java.util.*;
public class Solution {
    public void recursion(ArrayList<ArrayList<Integer>> res, int[] num,
                          ArrayList<Integer> temp, Boolean[] visited) {
        //临时数组满了，添加temp到res
        if (temp.size() == num.length) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for (int i = 0; i < num.length; ++i) {
            //已经加入临时数组的不需要再加入了
            if (!visited[i]) {
                if (i>0&& num[i] == num[i - 1]&&!visited[i-1]) {
                    continue;
                }
                temp.add(num[i]);
                visited[i] = true;  //标记为使用过
                recursion(res, num, temp, visited);
                //回溯到递归前状态，当前位置未被使用
                visited[i] = false;
                //移除最后加入的元素
                temp.remove(temp.size()-1);
            }
        }
    }
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        //排序后num就是有序的数组了
        Arrays.sort(num);
        //用于判断数组中某个位置是否加入了临时数组
        Boolean[] visited = new Boolean[num.length];
        //填充数组
        Arrays.fill(visited, false);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        //临时数组
        ArrayList<Integer> temp = new ArrayList<Integer>();
        //递归，res为最终结果数组
        recursion(res, num, temp, visited);
        return res;
    }
}