Sorting과 Backtracking 기반 중복 제거로 최적의 Subset 생성 구조 설계

Context

중복 원소가 포함된 정수 배열에서 모든 가능한 Subset을 생성하는 과제 수행. Brute Force 방식의 Pick/Not Pick 재귀 호출은 불필요한 중복 조합을 다수 생성하여 Set을 통한 사후 필터링 비용이 발생하는 한계 존재.

Technical Solution

• 배열 Sorting을 통한 중복 원소의 인접 배치로 식별 효율성 확보
• Backtracking 기반의 탐색 구조를 설계하여 상태 공간 트리 최적화
• 동일 재귀 레벨 내 이전 원소와 현재 원소의 동일 여부를 검사하는 조건문 도입
• i != ind && nums[i] == nums[i-1] 로직을 통한 중복 시작점 사전 차단
• 불필요한 분기 진입을 원천 제거하여 중복 Subset 생성 단계 자체를 생략