递归回溯：可以重复

题目：https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=295&tqId=700&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
解题思路：太久没有做了，之前也是做过类似的但是又给忘记了，跟没有重复项数字的全排列比较相似，区别在于有重复的数字，需要加以处理，也就是加入一个mark[]数组，标记是否遍历过。
首先把数组sort一下，比较方便。然后进行递归回溯。判断条件是一样的，如果list长度等于数组长度就把当前list加入总res列表结束递归，返回上一层，然后把最后一个元素去掉继续for循环遍历（不能忘记把当前位置标记为false标明已经遍历过）。在for循环中加入条件当i>0 &&此时的数等于它的上一个&&上一个没访问过(没访问过证明是回溯后将前面的置为false，所以此时避免重复得用 !mark[i-1] 满足要求然后跳过该数字)

import java.util.*;
public class Solution {
    //用于标记是否访问过
    boolean []mark;
    public ArrayList<arraylist<integer>> permuteUnique(int[] num) {
        //存储总的返回结果集
        ArrayList<arraylist<integer>> res = new ArrayList<>();
        //存储一个合法全排列
        LinkedList<integer> track = new LinkedList<>();

        mark = new boolean[num.length];
        //因为存在重复项，为了更好的处理，将数组先排序
        Arrays.sort(num);

        backtrack(num,res,track);

        return res;
    }

    public void backtrack(int[] num, ArrayList<arraylist<integer>> res, LinkedList<integer> track){
        //若 找到一个全排列，则将它加进结果集中，然后返回(回溯)
        if(track.size() == num.length){
            res.add(new ArrayList<integer>(track));
            return;
        }
        for(int i = 0; i < num.length; i++){
            // 当此时的被访问过
            // 当i>0 &&此时的数等于它的上一个&&上一个没访问过(没访问过证明是回溯后将前面的置为false，所以此时避免重复得用 !mark[i-1] 满足要求然后跳过该数字)
            // arr[1,1,1,2,3]
            // 1,1,1  1,1,2 1,1,3  前面两次回溯得到三个结果
            // 接下来再进行回溯，此时mark[1]被置为false
            // 此时按道理应该遍历到arr[2]这个位置
            // 1,arr[2] 然后后面再加进去，但是我们发现arr[2]==arr[1]，并且此时mark[1]==false
            // 证明它的已经访问过然后回溯的，所以我们跳过arr[2],直接从1,arr[3]开始
            // 也就是说此时得到全排列的结果将会是 1,2,1 1,2,3 而不再是 1,1 ··· 这些重复的了
            if(mark[i] || i>0 && num[i] == num[i-1] && !mark[i-1]){
                continue;
            }
            //添加进全排列数组中
            track.add(num[i]);
            //标记为已经访问
            mark[i] = true;
            //继续寻找下一个数
            backtrack(num,res,track);
            //将上一次全排列的结果中，最后一个数移除掉
            track.removeLast();
            //移除掉的数置为 未访问
            mark[i] = false;
        }
    }
}