부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션)금전등록기에 남아 있는 동전을 조합하여 필요한 거스름돈을 만들 수 있는지 확인해보자.필요한 잔돈이 73270원이고, 10000원권, 1000원권과 500원, 100원, 50원, 10원 동전들이 전체 100개가 들어있다면?가능한 모든 조합을 시도해보면서 거스름돈의 금액을 맞추는 것은 너무 복잡해지고 실제로 구현하는 것은 너무 복잡하고 비현실적이러한 문제를 부분집합의 합 문제(subset sum problem)이라고 한다"음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?"ex) S = {13, 79, 45, 29}, x = 42 --> True원소의 ..