[C] 백준 1182번 부분수열의 합

링크
https://www.acmicpc.net/problem/1182

문제

---

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

---

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

---

5 0
-7 -3 -2 5 8

예제 출력 1

---

1

아이디어 스케치

---

백트래킹과 재귀함수를 이용하여 문제를 해결하였다.

로직을 살펴보면

인덱스가 수열의 범위를 벗어난 경우에는 더이상 탐색하지 않는다.

부분 수열의 합에 현재 선택한 arr[idx]를 더한 후 부분 합이 구하려는 S와 같다면 cnt를 1 증가시킨다.

이후 두 가지 경우로 탐색의 방향을 나눌 수 있는데,

첫 번째는 현재 선택한 arr[idx]를 sub_sum에 포함한 후 다음 idx를 탐색하는 경우와
두 번째는 현재 선택한 arr[idx]를 sub_sum에 포함하지 않고 다음 idx를 탐색하는 경우이다.

위 로직을 이용하면 모든 부분 수열의 합을 탐색할 수 있다.

전체 코드

---

#include <stdio.h>
#include <stdlib.h>

int cnt = 0;
int N, S;
int* arr;

void sumOfSubset(int idx, int sub_sum) {
	if (idx >= N) return;	// 인덱스가 수열의 범위를 벗어날 경우

	sub_sum += arr[idx];	// 부분 합에 현재 arr[idx]를 추가

	if (sub_sum == S) cnt++;	// 부분 합이 S와 같다면 cnt 1 증가

	// 현재 선택한 arr[idx]를 sub_sum에 포함하는 경우
	sumOfSubset(idx + 1, sub_sum);

	// 현재 선택한 arr[idx]를 sub_sum에 포함하지 않는 경우
	sumOfSubset(idx + 1, sub_sum - arr[idx]);
}

int main()
{
	scanf("%d %d", &N, &S);

	// 동적할당
	arr = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	// 함수 실행
	sumOfSubset(0, 0);

	printf("%d", cnt);	// 결과 출력

	// 메모리 해제
	free(arr);

	return 0;

}

제출 결과

---