[LeetCode] 47. Permutations II

이전 문제와는 다르게 고유한 순열을 반환해야한다.

즉 Map을 사용하여 숫자들의 출현 빈도를 파악하고 출연한 빈도 내에서만 가능한 순열을 모두 구해준 후 결과를 반환한다.

해당 문제또한 백트레킹을 활용하여 모든 가능한 경우의 수를 조회한다.

😎풀이

function permuteUnique(nums: number[]): number[][] {
    const result = [];
    
    const countMap = new Map<number, number>();
    
    // 숫자의 출현 횟수를 계산
    for (const num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    
    // 백트래킹 함수
    function backtrack(current: number[]) {
        // 현재 순열의 길이가 원래 배열의 길이와 같으면 결과에 추가
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        
        // countMap을 순회하면서 가능한 모든 숫자에 대해 시도
        for (const [num, count] of countMap) {
            if (count > 0) {
                // 현재 숫자를 선택
                current.push(num);
                countMap.set(num, count - 1);
                
                // 재귀적으로 다음 숫자 선택
                backtrack(current);
                
                // 백트래킹: 선택을 취소하고 다음 가능성을 시도
                current.pop();
                countMap.set(num, count);
            }
        }
    }
    
    // 백트래킹 시작
    backtrack([]);
    
    return result;
}