부분집합 합 문제

1 개요

subset sum problem

부분집합 합 문제

• 계산 복잡도 이론과 암호학에 관련된 문제
• 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
• 예를 들어 { −7, −3, −2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 됨
• 부분집합의 합 조건을 0 대신 일반적인 정수 s로 일반화할 수 있음
• 배낭 문제의 특수한 경우로 생각할 수 있음
• 집합을 합이 같은 두 집합으로 나누는 문제인 분할 문제는 이 문제의 특수한 경우임

2 같이 보기

• 3SUM
• 부분집합
• 배낭 문제
• Merkle–Hellman 배낭 암호시스템

3 참고

• 위키백과 "부분집합 합 문제"
• 영어 위키백과 "Subset sum problem"