부분집합 합 문제

1 개요

subset sum problem

부분집합 합 문제

• 계산 복잡도 이론과 암호학에 관련된 문제
• 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
• 예를 들어 { −7, −3, −2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 됨

2 같이 보기

• 3SUM
• Merkle–Hellman 배낭 암호시스템

3 참고

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