2021.07.22
부분집합의 합 문제(Subset Sum Problem)
부분집합의 합 문제(Subset Sum Problem) 부분집합의 합 문제를 한 문장으로 표현하면 다음과 같음. 음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가? 부분집합의 합 문제의 예 S = { 13, 79, 45, 29 } x = 42 → True (13 + 29) x = 25 → False 집합 S가 S = { 13, 79, 45, 29 } 형태로 주어질 경우, S로부터 다음과 같은 16개의 부분집합을 추출할 수 있음. { } { 13 } { 79 } { 45 } { 29 } { 13, 79 } { 13, 45 } { 13, 29 } { 79, 45 } { 79, 29 } { 45, 29 } { 13, 79..
