[Backtracking: Subset 부분집합] 90. Subsets II

90. Subsets II

 

https://youtu.be/Vn2v6ajA7U0?si=w1awdAmx7zve9Tqv

 

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # Sort the input list to group duplicates together
        # 입력 리스트를 정렬하여 중복된 숫자를 연속적으로 배치
        nums.sort()

        # List to store all unique subsets
        # 모든 고유한 부분집합을 저장할 리스트
        res = []

        # Backtracking function
        # 백트래킹 함수 정의
        def backtrack(subset, idx):
            # Base case: If we reach the end of nums
            # 기저 조건: nums의 끝에 도달했을 경우
            if idx == len(nums):
                # Add the current subset to the results
                # 현재 부분집합을 결과 리스트에 추가
                res.append(subset.copy())
                return

            # Explore all subsets that include nums[idx]
            # nums[idx]를 포함하는 모든 부분집합 탐색
            subset.append(nums[idx])  # Add nums[idx] to the subset
            backtrack(subset, idx + 1)  # Move to the next index
            subset.pop()  # Remove nums[idx] after backtracking (restore state)

            # Explore all subsets that do NOT include nums[idx]
            # nums[idx]를 포함하지 않는 모든 부분집합 탐색
            # Skip duplicates: Increment idx while the next number is the same as the current number
            # 중복을 건너뜀: 다음 숫자가 현재 숫자와 같으면 idx 증가
            while idx + 1 < len(nums) and nums[idx] == nums[idx + 1]:
                idx += 1
            backtrack(subset, idx + 1)  # Move to the next unique number

        # Start backtracking with an empty subset
        # 빈 부분집합으로 백트래킹 시작
        backtrack([], 0)
        
        # Return the result containing all unique subsets
        # 모든 고유한 부분집합이 담긴 결과 반환
        return res

 

최종 코드

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # The solution set must not contain duplicate subsets. 
        # 중복 금지
        subset, curset = [], []

        # 중복 금지를 위해, nums 정렬 <-- 중요!!
        nums.sort()

        def help(i, Nums, SubSet, CurSet):
            if i >= len(Nums):
                SubSet.append(CurSet.copy())
                return

            # nums[i] 추가하고, i+1
            CurSet.append(Nums[i])
            help(i+1, Nums, SubSet, CurSet)

            # nums[i] 제거하고, i+1
            CurSet.pop()
            while i+1 < len(Nums) and Nums[i] == Nums[i+1]:
                i+=1
            help(i+1, Nums, SubSet, CurSet)

        help(0, nums, subset, curset)
        return subset

 

중복 방지를 위해, 꼭!!! nums 정렬 해야함!!