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

문제

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

1182번: 부분수열의 합

문제풀이

다음칸을 선택, 선택하지 않는 경우인 두 경우를 나누어 DFS함수를 실행시킨다.

선택한다면 visit함수에 push_back으로 해당 idx번째 값을 넣어준다.

idx가 N-1이 되었다면 visit벡터의 값들의 합을 구해 S와 같은지를 비교한다.

모두 선택하지 않는 경우는 개수에 포함이 안되므로 visit의 size가 0이 아닐 때라는 조건을 걸어둔다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
int N, S;
vector<int>seq;
vector<int>visit;
int answer;

void DFS(int idx) {
	int idx2(0);
	if (idx == N - 1 && visit.size() != 0) {
		int sum(0);
		for (idx2 = 0; idx2 < visit.size(); ++idx2)
			sum += visit[idx2];
		if (sum == S) ++answer;
		return;
	}
	if (idx + 1 < N) {
		visit.push_back(seq[idx + 1]);
		DFS(idx + 1);
		visit.pop_back();
		DFS(idx + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> S;
	int idx(0);
	seq = vector<int>(N, 0);
	for (idx = 0; idx < N; ++idx)
		cin >> seq[idx];

	DFS(0);
	visit.push_back(seq[0]);
	DFS(0);
	cout << answer;
}