47-全排列-ii.md

47-全排列-ii

原题

全排列-ii 中是原先全排列 的一次条件的筛选，之前条件是序列不重复，现在是序列是包含重复数字的序列 首先去看，应该好

const permuteUnique = function (nums) {
    const res = [];
    const used = {};

    const backtrack = (path) => {
        if (path.length === nums.length) {
            res.push(path.slice());
        }

        for (let i = 0; i < nums.length; i++) {
            // 全排列i和全排列ii的区别就是这里是否需要条件判断去重
            if (
                used[i]
                // i > 0 && nums[i] === nums[i - 1] 我理解，是判断前后是否一致，如果一致就 continue
                // 但是 !used[i - 1] 我就不太理解了
                || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])
            ) {
                continue;
            }

            used[i] = true;
            path.push(nums[i]);
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    }

    nums.sort((x, y) => x - y);
    backtrack([]);
    return res;
}

let result = permuteUnique([1,1,2]);
console.log(result);

判断重复条件解释：

要解决重复问题，我们只要设定一个规则，保证在填第n个数的时候重复数字只会被填入一次即可。 而在本题解中，我们选择对原数组排序，保证相同的数字都相邻， 然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

(i > 0 && nums[i] === nums[i - 1] && !used[i - 1])