백준 1182번 부분수열의 합 // C++

문제

 

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

입력

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

출력

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

 

---

 

풀이

 

부분 수열의 크기는 1~N까지 가능하다. 이 때 수열의 합이 S가 되는 경우의 수를 출력하면 된다.

 

먼저, 크기가 1인 경우는 입력을 받으면서 S와 값을 비교하여 세주었다.

 

나머지 2~N까지의 경우는 각각 최대 크기에 따라 dfs를 통하여 합이 S가 되는지 확인하였다.

 

---

 

코드

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

using namespace std;

int N, S;
vector<int> num;
vector<int> v;
int res = 0;
bool visit[21] = { false, };

void dfs(int index, int size, int max_size);

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

	int input;

	for (int i = 0; i < N; i++) {
		cin >> input;

		if (input == S)
			res++;
		num.push_back(input);
	}

	for (int i = 2; i <= N; i++) {
		dfs(0, 0, i);
	}

	cout << res << "\n";

	return 0;
}

void dfs(int index, int size, int max_size) {
	if (size == max_size) {
		int sum = 0;
		for (int i = 0; i < v.size(); i++) {
			sum += v[i];
		}
		if (sum == S)
			res++;

		return;
	}

	for (int i = index; i < N; i++) {
		if (!visit[i]) {
			visit[i] = true;
			v.push_back(num[i]);
			dfs(i + 1, size + 1, max_size);
			v.pop_back();
			visit[i] = false;
		}
	}
}