[LeetCode] 90. Subsets Ⅱ

문제 출처: https://leetcode.com/problems/subsets-ii/

Subsets II - LeetCode

 

문제

중복이 허용된 정수 배열 nums가 주어지면, 가능한 모든 부분집합(멱집합)을 반환하라.

 

답에는 중복된 부분집합이 존재해서는 안된다. 어떤 순서로든 답을 반환해도 된다.

 

예제

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

Input: nums = [0]
Output: [[],[0]]

 

풀이

먼저, 찾아야 하는 답이 주어지는 nums의 순열의 집합이라는 점을 주목할 수 있다.

 

다음과 같이 재귀를 활용하여 어떤 배열의 순열을 구할 수 있다.

function premutation(arr, idx, permu, limit, ans) {
    if (limit == 0) {
    	ans.push(permu.slice());
        return;
    }
    
    for (let i = idx; i < arr.length; i++) {
    	permu.push(arr[i]);
        premutation(arr, i+1, permu, limit-1, ans);
        permu.pop();
    }
}

여기서 주의해야 할 점은 주어지는 배열에는 중복된 값이 존재할 수 있고, 중복된 값으로 인해서 같은 순열이 나올 수 있다는 점이다.

 

이 상황을 타개하기 위해서 다음 방식을 사용하였다.

• nums를 정렬
• 찾아진 부분집합을 집합(혹은 맵) 자료구조로 저장

정렬을 사용하는 이유는 동일한 부분집합을 효율적으로 파악하기 위함이다.  예를 들어 [1, 2]와 [2, 1]은 동일한 부분집합이지만 배열 내부의 순서가 다르다. 때문에 이 두 집합이 같은지 파악하기 위해서는 각 원소가 서로에게 있는지 여부를 체크해야 한다. 만약 nums를 정렬한 이후, 순열을 구하게 된다면 언제나 찾아지는 부분집합은 오름차순으로 정렬되어 있기 때문에 동일한 부분집합을 판별함에 있어 조금 더 편리하게 판별할 수 있다.

 

다음으로 각 부분집합을 집합(혹은 맵) 자료구조를 이용해서 저장하는 것이다. 단, 단순히 배열을 저장하는 것이 아닌 배열 내부의 원소를 하나로 엮어 문자열로 저장한다. 예를 들어, 배열 [1, 2, 3]이라면 "123"의 형태로 저장하는 것이다. 이와 같은 형태로 집합 자료구조에 저장하게 되면, 단순히 조회하는 것만으로 해당 배열이 이전에 찾아진 배열인지 아닌지 찾을 수 있게 된다.

 

최종 코드는 다음과 같다.

var subsetsWithDup = function(nums) {
    const arr = nums.slice();
    arr.sort((a, b) => a - b);
    
    const powerSet = new Set();
    const subsets = [];
    
    function findSubset(arr, idx, permu, limit) {
        if (limit == 0) { 
            const key = permu.join('');
            if (powerSet.has(key)) { return; }
            powerSet.add(key);
            subsets.push(permu.slice());
            return;
        }
        
        for (let i = idx; i < arr.length; i++) {
            permu.push(arr[i]);
            findSubset(arr, i+1, permu, limit-1);
            permu.pop();
        }
    }
    
    for (let i = 0; i <= arr.length; i++) {
        findSubset(arr, 0, [], i)   
    }
    
    return subsets;
};

 

Github: 90.js

GitHub - opwe37/Algorithm-Study