Partition Problem

 

Subset Sum 의 약식버전

부분집합 A의 합=전체 합/2. 즉, Subset Sum 문제에서 목표 합 K = total/2로 두고 풀면 Partition 문제와 동일하다.

 

S={3,1,1,2,2,1}

• 합 T=10T = 10T=10 → 짝수 → 목표: Subset 합 = 5
• 가능한 부분집합: {3, 2}, {1,1,2,1} 등
• → Subset Sum 문제로 변환 완료