LeetCode Permutations || (JavaScript), 순열

링크 : https://leetcode.com/problems/permutations-ii/

문제 설명

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

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

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

---

문제 풀이

dfs를 이용하여 풀이

1. 중복 생성을 방지하기 위해 이전 값과 비교를 해야하므로 nums 배열을 오름차순으로 정렬

2. dfs내부 반복문

• 같은 순열을 생성하지 않기 위해 visited 배열을 사용하여 중복 생성 방지
• 또한, 시작하는 값이 같을 경우 건너 뛰도록 비교하는 if문 추가
  • 현재 값이 사용이 안되었고 && 이전 값이랑 같을 때 && 만약 이전 값이 사용되지 않았다면
    • 현재 값이 선택되면 안됨 (기준은 무조건 이전 값이므로 이전 값이 사용 안되었는데 현재를 선택한다? -> 중복 발생) 
  • `if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) continue;`

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const answer = [];
    const visited = Array.from({length: nums.length}, () => false);

    nums.sort((a, b) => a - b);

    const dfs = (arr) => {
        if (arr.length === nums.length) {
            answer.push([...arr]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) {
                    continue;
                }

                visited[i] = true;
                arr.push(nums[i]);

                dfs(arr);

                visited[i] = false;
                arr.pop();
            }
        }
    }

    dfs([]);

    return answer;
};

---

결론

dfs에 중복 생성 방지를 위해 2가지의 로직을 추가

1. visited 배열을 통해 특정 값이 중복 선택되지 않도록 검사

2. 최종 선택된 배열이 unique하게 하기 위해 sort와 이전 값을 비교하는 로직을 추가