[LeetCode] 47. Permutations II

https://leetcode.com/

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

 

Code :

var permuteUnique = function(nums) {
    // 결과를 저장할 배열을 선언합니다.
    const result = [];
    // 배열을 정렬합니다.
    nums.sort((a, b) => a - b);
    // 백트래킹 함수를 정의합니다.
    const backtrack = (current, remaining) => {
        // 재귀 호출 기저 조건: 남은 요소가 없는 경우 현재 배열을 결과에 추가하고 종료합니다.
        if (remaining.length === 0) {
            result.push(current.slice());
            return;
        }
        // 중복된 요소를 건너뛰며 각 요소에 대해 재귀적으로 백트래킹을 수행합니다.
        for (let i = 0; i < remaining.length; i++) {
            if (i > 0 && remaining[i] === remaining[i - 1]) {
                continue;
            }
            current.push(remaining[i]);
            backtrack(current, remaining.slice(0, i).concat(remaining.slice(i + 1)));
            current.pop();
        }
    };
    // 백트래킹 함수를 초기 호출합니다.
    backtrack([], nums);
    // 결과 배열을 반환합니다.
    return result;
};

 

Solutions Code : 

var permuteUnique = function(nums) {
    // 결과를 저장할 배열을 초기화합니다.
    const res = [];
    // 각 요소의 출현 빈도를 저장할 객체를 초기화합니다.
    const countMap = {};
    // nums 배열을 순회하면서 각 요소의 출현 빈도를 저장합니다.
    for (let i = 0; i < nums.length; i++) {
        const curVal = nums[i];
        // 출현 빈도가 없는 경우 1로 초기화하고, 있는 경우 1을 더합니다.
        if (!countMap[curVal]) {
            countMap[curVal] = 1;
        } else {
            countMap[curVal] += 1;
        }
    } 
    // 깊이 우선 탐색 함수를 호출합니다.
    dfs(nums, [], countMap, res);
    // 결과 배열을 반환합니다.
    return res;
};

// 깊이 우선 탐색 함수를 정의합니다.
function dfs(nums, path, countMap, res) {
    // 기저 조건: 경로의 길이가 nums의 길이와 같아지면 결과 배열에 추가합니다.
    if (path.length === nums.length) {
        return res.push([...path]);
    }
    // countMap을 순회하면서 각 요소의 출현 빈도를 확인하고 백트래킹을 수행합니다.
    for (const num in countMap) {
        const numCount = countMap[num];
        // 출현 빈도가 0이면 건너뜁니다.
        if (numCount === 0) continue;
        // 요소를 path에 추가하고 출현 빈도를 1 감소시킵니다.
        path.push(num);
        countMap[num] -= 1;
        // 재귀 호출을 통해 백트래킹을 수행합니다.
        dfs(nums, path, countMap, res);
        // 요소를 path에서 제거하고 출현 빈도를 1 증가시킵니다.
        path.pop();
        countMap[num] += 1;
    }
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode