6011 : 백트래킹 — 부분합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수가 주어질 때, 이 중 원소를 하나 이상 선택하여 그 합이 정확히 $S$가 되는 부분집합의 개수를 구하십시오.
백트래킹 탐색을 기본으로 하되, 원소 수가 $N \le 30$으로 크므로 단순 DFS 백트래킹(시간 복잡도 $O(2^{30})$)은 시간 초과가 날 수 있습니다.
정렬 후 합이 $S$를 넘어가면 탐색을 중지하거나, 전체 수들의 절반씩 나누어 부분합을 구한 뒤 병합하는 중간에서 만나기(Meet in the Middle) 기법 등을 사용해 최적화하십시오.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 20$ (정수)
• 목표 합 $S$: $1 \le S \le 10^6$ (정수)
• 각 원소: $1 \le a_i \le 10^5$ (정수)
백트래킹 탐색을 기본으로 하되, 원소 수가 $N \le 30$으로 크므로 단순 DFS 백트래킹(시간 복잡도 $O(2^{30})$)은 시간 초과가 날 수 있습니다.
정렬 후 합이 $S$를 넘어가면 탐색을 중지하거나, 전체 수들의 절반씩 나누어 부분합을 구한 뒤 병합하는 중간에서 만나기(Meet in the Middle) 기법 등을 사용해 최적화하십시오.
[제약 조건]
• 원소 개수 $N$: $1 \le N \le 20$ (정수)
• 목표 합 $S$: $1 \le S \le 10^6$ (정수)
• 각 원소: $1 \le a_i \le 10^5$ (정수)
입력 설명
첫째 줄에 정수의 개수 $N$과 목표 합 $S$가 공백으로 구분되어 주어집니다. ($1 \le N \le 30$, $1 \le S \le 10^7$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. (원소의 값은 $1$ 이상 $10^6$ 이하의 자연수)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. (원소의 값은 $1$ 이상 $10^6$ 이하의 자연수)
출력 설명
합이 정확히 $S$가 되는 부분집합의 개수를 출력합니다. (공집합은 정답에서 제외합니다)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
수들을 절반인 $N/2$개씩 두 그룹으로 쪼갠 뒤, 각 그룹에서 만들 수 있는 모든 부분집합의 합들을 구합니다(각각 최대 $2^{15}$개). 이후 한쪽 합 $X$와 다른 쪽 합 $S-X$의 곱을 누적하는 방식을 사용하면 $O(2^{N/2})$로 해결됩니다.