7298 : 재귀 + 가지치기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수 중 몇 개를 선택하여 합이 정확히 $S$가 되는 조합의 수를 구하십시오.
백트래킹으로 탐색하되, 남은 원소의 합이 $S$보다 작으면 즉시 리턴하는 가지치기(Pruning)를 구현해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
백트래킹으로 탐색하되, 남은 원소의 합이 $S$보다 작으면 즉시 리턴하는 가지치기(Pruning)를 구현해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$과 목표 합 $S$가 주어집니다. ($1 \le N \le 25$, $|S| \le 10^6$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
합이 $S$가 되는 조합의 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
각 원소를 선택/미선택으로 재귀합니다. 가지치기: 남은 원소들의 합이 $S - \text{현재합}$보다 작으면 즉시 종료합니다. 정렬 후 탐색하면 효율이 높아집니다.