[Backtracking: Permutations] 47. Permutations II

47. Permutations II

 

"중복 숫자가 포함된 리스트에서 모든 유일한 순열을 반환하라"는 문제입니다.

---

✅ 핵심 포인트 요약

• nums에 중복 원소가 존재할 수 있음
• 따라서 단순한 백트래킹으로 모든 순열을 생성하면 중복된 결과가 포함됨
• → 정렬 + 백트래킹 중 중복 조건 체크로 중복 제거 필요

---

✅ 최적 풀이 (정렬 + used[] + 가지치기)

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 결과를 저장할 리스트
        res = []

        # 중복 숫자를 인접하게 만들어 중복 제거가 쉽게 되도록 정렬
        nums.sort()

        # 숫자의 사용 여부를 표시할 리스트 (index 기반)
        used = [False] * len(nums)

        # 백트래킹 함수 정의
        def backtrack(path):
            # 순열 완성 조건: path의 길이가 nums의 길이와 같을 때
            if len(path) == len(nums):
                res.append(path[:])  # path 복사 후 결과에 저장
                return

            # nums의 각 인덱스를 하나씩 확인
            for i in range(len(nums)):
                # 이미 사용한 숫자면 건너뜀
                if used[i]:
                    continue

                # 중복 제거 조건:
                # - 현재 숫자와 이전 숫자가 같고
                # - 이전 숫자가 아직 사용되지 않았다면 (같은 레벨에서 중복)
                #   → 중복된 순열이므로 건너뜀
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                # 현재 숫자 사용 처리
                used[i] = True
                path.append(nums[i])

                # 다음 숫자 선택하러 재귀 호출
                backtrack(path)

                # 백트래킹: 현재 선택을 취소하고 되돌아감
                path.pop()
                used[i] = False

        # 초기 호출: 빈 path와 초기 used 상태
        backtrack([])

        # 중복 없는 모든 순열 반환
        return res