LeetCode Subsets ll (JavaScript), backtracking

링크 : https://leetcode.com/problems/subsets-ii/description/

문제 설명

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

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

---

문제 풀이

1. set 자료구조를 이용해 중복 제거

중복되는 subset에 대해서 넘어가기 위해 set에 저장하여 중복 저장이 안되도록 함.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const answer = [];
    const set = new Set();
    nums.sort((a, b) => a - b);

    const dfs = (index, arr) => {
        answer.push([...arr]);

        for (let i = index; i < nums.length; i++) {
            if (!set.has(JSON.stringify([...arr, nums[i]]))) {
                dfs(i + 1, [...arr, nums[i]]);
                set.add(JSON.stringify([...arr, nums[i]]));
            }
        }
    }

    dfs(0, []);

    return answer;
};

 

2. backtracking 이용 (권장)

subset을 만드는 과정을 backtracking을 이용해서 표현해보면 위에 그림과 같다.

특정 요소를 선택할 경우 / 안 할 경우로 나눠서 탐색을 진행

핵심은 탐색을 하는 과정에서 중복된 subset이 존재할 수 있다는 것이다. (파란색 부분)

즉, 0번째 요소 2에서 만들어지는 [2, 3], [2]는 1번째 요소 2로 만들어지는 [2, 3], [2]와 중복되는 문제가 발생한다.

이러한 중복을 방지하기 위해 특정 요소를 선택 안할 경우에 대해 탐색을 진행한 요소와 겹치는 값은 건너뛰도록 index를 조정해주면 된다.

-> 0번째에서 2를 검사했으면 1번째에 나오는 2에 대해 탐색을 진행 안해도 됨.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const answer = [];
    const subset = [];
    nums.sort((a, b) => a - b);

    const backtracking = (index) => {
        if (index === nums.length) {
            answer.push([...subset]);
            return;
        }

        subset.push(nums[index]);
        backtracking(index + 1);
        subset.pop();

        // 중복 숫자 건너 뛰기
        while (index < nums.length && nums[index] === nums[index + 1]) {
            index++;
        }

        backtracking(index + 1);
    }

    backtracking(0);

    return answer;
};

---

결론

1번의 경우 매번 배열을 문자열로 바꾸는 비용과 set함수를 관리하는 비용을 고려해볼 때

O(N*(2^N)*N)의 시간 복잡도와 O(N*(2^N))의 공간 복잡도를 가진다.

 

1번을 좀 더 효율적으로 변경하기 위해 backtracking을 이용하여 풀이하게 되면

O(N*(2^N))의 시간 복잡도와 O(N)의 공간 복잡도로 문제를 해결 할 수 있다.