9. DP 연습 - 부분집합의 합

1. 개요

DP 연습.

부분집합의 원소들의 합으로 입력한 합 구하기 문제.

재귀 아이디어

부분집합의 끝에 있는 원소의 합을 입력한 합에서 뺀 나머지를 합을 구하는 방법

+

현재 검사 원소를 제외한 나머지 원소로 입력한 합을 구하는 방법

DP 아이디어

초기화 -> 현재 검사 값이 현재 검사 원소보다 크면 이를 뺀 이전 결과가 나눠지면 메모 테이블에 성공을 뜻하는 1입력.

맨 마지막 테이블 원소값이 1이면 나누어짐, 0이면 실패.

2. 문제

주어진 부분 집합에서 각각의 원소를 추출하여 그 합이 입력한 SUM이 되게 하시오.

3. 전체코드 및 출력

3-1) 전체코드

3-2) 출력