Backtracking: 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