문제

문제 유형: 브루트포스 알고리즘 백트래킹
난이도: 실버Ⅱ

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

---

풀이

주어진 수열에서 숫자를 골라 부분 수열을 만들어, 수열의 합이 S가 되는 경우를 구한다.
기본적으로 수열을 구할 때 재귀 DFS가 쓰이기 때문에 DFS를 써야겠다고 생각했다.

부분 수열

주어진 전체 수열에서 부분 수열을 구할 때를 생각해보자.

전체 수열의 원소를 선택할 때는

1. 선택함
2. 선택하지 않음

두 가지 경우가 있다.

마찬가지로 합을 구할 때도

1. 원소를 더함
2. 원소를 더하지 않음

두 가지 경우이다.

따라서 전체 수열의 0번째~ N번째 원소까지 탐색하면서 더할지 더하지 않을지만 고려해주면 된다.
어떻게 구현할 수 있을까?

DFS

원소를 더하는 경우와 더하지 않는 경우 모두를 고려해야 하므로

1. i번째 원소를 더하는 경우
   DFS(Index + 1, Sum + arr[Index])
2. i번째 원소를 더하지 않는 경우
   DFS(Index + 1, Sum)

두 가지 모두를 호출한다.

호출시 현재까지 탐색한 원소의 위치와 선택한 원소의 합을 계속해서 넘겨줌에 주의한다.
0~N번째 원소까지 모두 탐색 완료 하였을때 확인한 합이 S와 같은 경우, 카운트를 세고 출력한다.

---

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, Sum;
int Ans = 0;
vector<int> arr;

void solve(int idx, int tmp) {
	if (idx == N) return; // idx N-1 까지 탐색한 경우 종료
	if (tmp + arr[idx] == Sum) Ans++; // return을 안함에 주의

	solve(idx + 1, tmp); // idx 수를 더하지 않는 경우
	solve(idx + 1, tmp + arr[idx]); // idx 수를 더하는 경우
}

int main() {
	cin >> N >> Sum;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	solve(0, 0);
	cout << Ans;

	return 0;
}