/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
function permuteUnique( num ) {
    num.sort((a, b) => a - b);

    let res = [], track = [], used = Array(num.length).fill(false);

    function backTrack(num, track) {
        if(track.length === num.length) {
            res.push([...track]);
            return;
        }

        for(let i = 0; i < num.length; i++) {
            // used[i] 如果已经使用过了，就跳过
            // 如果当前取的数和前一个数一样,也跳过。 !used[i-1] 特别标记是另外一条分支走完的情况
            if(used[i] || (i > 0 && num[i] === num[i-1] && !used[i - 1])) continue

            track.push(num[i]);
            used[i] = true;

            backTrack(num, track);
            
            track.pop();
            used[i] = false;
        }
    }

    backTrack(num, track, 0);

    return res;
}

Array.prototype.top = function () {
    return this[this.length -1];
}

module.exports = {
    permuteUnique : permuteUnique
};

思路：

这道题和那道没有重复项数字的全排列做法一致，只是需要添加一个used标记那个数字用到了还是没用到。

回溯法遍历其实就是便利一颗多叉树，画出多叉树就会清楚多一些：

1，1，2

1，2，1

遍历到第二个1的时候，发现 num[i] === num[i-1] 和前一个1相等了（后续结点情况会重复），并且前面的1的分支已经走完了，这第二个1就跳过。

2，1，1

遍历结点2的时候，走完了左边的分支，到了右边的分支，此时又发现和前面的遍历元素相等了num[i] === num[i-1] (同级结点),那后续结点的遍历又没有必要了。

所以最终遍历结果就是[[1,1,2], [1,2,1], [2,1,1]]