[leetcode] 47. Permutations2

문제

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Constraints

• 1 <= nums.length <= 8
• 10 <= nums[i] <= 10

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var permuteUnique = function (nums) {

    const solutions = [];
    nums.sort((a, b) => a - b);
    backtracking(nums, solutions, [], new Set());
    return solutions;

};

const backtracking = (nums, solutions, current, used) => {
    if (current.length === nums.length) {
        return solutions.push(current.slice());
    }

    for (let i = 0; i < nums.length; i++) {
        if (used.has(i)) {
            continue;
        }

        previous is used
        if (i > 0 && nums[i] === nums[i - 1] && !used.has(i - 1)) {
            continue;
        }

        current.push(nums[i]);
        used.add(i);
        backtracking(nums, solutions, current, used);
        current.pop();
        used.delete(i);
    }
}

if문 if (i > 0 && nums[i] === nums[i - 1] && !used.has(i - 1)) 조건은 중복을 체크해 주는 것 이다.

1. 일단 nums 안에 있는 i가 1보다 커야하고
2. nums 배열안에 값이 중복되면 num[i] === num[i-1]
3. 배열 안의 현재 i 값과 i-1의 값이 같고(2), for문이 현재 i-1 인덱스에 방문하지 않으면 무조건 중복값이 된다.