부분집합 합 문제

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

이 문제에서 부분집합의 합 조건을 0 대신 일반적인 정수 s로 일반화할 수 있고, 또한 이 문제는 배낭 문제의 특수한 경우로 생각할 수 있다. 또한 집합을 합이 같은 두 집합으로 나누는 문제인 분할 문제는 이 문제의 특수한 경우이다.