[1182번] 부분수열의 합

1182번: 부분수열의 합

 

www.acmicpc.net

모든 경우를 다 실행해 보는 완전탐색 문제다.

재귀호출을 이용해서 풀면된다.

재귀 호출 시 2가지 경우를 나눠서 호출하는데,

1. 현재 방문지역(index)의 값을 더해준 뒤 다음을 호출

2. 현재 방문지역의 값을 더해주지 않고 다음을 호출

원소의 개수가 3개인 배열을 예로 들어 그림으로 표현해 보면

이런 식으로 볼 수 있다.

/*1182번 부분수열의 합*/
#include <iostream>
using namespace std;
int N, S, cnt;
int arr[20];

void Search(int index,int sum) {
	int temp = sum + arr[index];
	if (index >= N) return;
	if (temp == S) cnt++;
	Search(index + 1, sum);//현 인덱스의 값을 더하지 않았을 때
	Search(index + 1, temp);//현 인덱스의 값을 더했을 떄
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> arr[i];
	Search(0, 0);
	cout << cnt;
}