leetcode.com 90. Subsets II

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

파이썬 소스: https://bit.ly/3VY2v9T

 

이 문제를 풀기 전에 꼭, 아래 leetcode 78번 문제를 꼭 풀어 보시기를 추천 드립니다.

leetcode.com 78. Subsets 문제 링크: https://leetcode.com/problems/subsets/description/ 문제 풀이: https://codapul.blogspot.com/2024/04/leetcodecom-78-subsets.html 파이썬 소스: https://bit.ly/3VY2v9T

 

이 문제가 78번과 다른 점은 nums 배열에 중복된 숫자가 들어 있다는 점입니다.

Example 1번을 보면, nums = [1, 2, 2]로 2가 2개 들어 있습니다.

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

이렇게 보면, 어떻게 접근해야 할지 잘 모르겠습니다. 우선 길이를 기준으로 정렬을 해보겠습니다.

Output: [[],[1],[2],[1,2],[2,2],[1,2,2]]

길이가 짧은 순서대로 정렬을 해놓고 보니, 조합과 비슷해 보이지만, 중복된 두개의 2때문에 아직 구현 방법이 떠오르지 않습니다.

nums가 [1,2,3] 이였다고 가정을 하고, 길이가 0~3인 조합을 구해 보면 아래와 같습니다.

[[],[1],[2],[3],[1,2],[1,3],[2,2],[2,3],[1,2,3]]

여기서 3이였던, 숫자를 다시 2로 바꿔 보겠습니다.

[[],[1],[2],[2],[1,2],[1,2],[2,2],[2,2],[1,2,2]]

굵은 글씨체 [2]는 앞에 [2]의 중복 이구요,

굵은 글씨체 [1, 2]는 앞에 [1, 2]의 중복이며,

굵은 글씨체 [2, 2]는 앞에 [2, 2]의 중복입니다.

 

위와 같은 중복은, 2가 두개 nums에 들어 있기 때문에 발생하는 중복입니다.

따라서, leetcode 78번에서 구현했던, 조합(combinations)코드에서, 중복을 제거 하는 코드만 추가 하면, 이 문제의 답을 구할 수 있습니다.

 

leetcode 78번에서 1개의 조합을 구하게 되면, stop condition인 length == 0이 True가 됩니다.

def mycombination(nums: List[int], length: int, answer: List):     def rec(nums: List[int], idx_begin: int, length: int, pathes: List, answer: List):         if length == 0:             if pathes not in answer:                 answer.append(pathes)             return

 

하지만, 이 문제에서는 중복된 조합이 발생하기 때문에, answer에 pathes를 추가히기 전에, 이미 answer가 pathes를 가지고 있는지 확인하는 코드를 추가합니다.

def mycombination(nums: List[int], length: int, answer: List):     def rec(nums: List[int], idx_begin: int, length: int, pathes: List, answer: List):         if length == 0:             if pathes not in answer:                 answer.append(pathes)             return

기존에 구한 조합은 answer에 추가 하지 않습니다.

 

 이문제를 구현한 전체 코드는 아래와 같습니다.

from typing import List def mycombination(nums: List[int], length: int, answer: List):     def rec(nums: List[int], idx_begin: int, length: int, pathes: List, answer: List):         if length == 0:             if pathes not in answer:                 answer.append(pathes)             return         for idx in range(idx_begin, len(nums)):             n = nums[idx]             rec(nums, idx + 1, length - 1, pathes + [n], answer)         return answer     rec(nums, 0, length, [], answer)     return answer class Solution:     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:         answer = []         nums.sort()         for length in range(len(nums) + 1):             answer_local = []             mycombination(nums, length, answer_local)             answer += answer_local         return answer

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul