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

1182번: 부분수열의 합

N개의 정수 중에 순서 상관없이 1~N만큼 뽑아 더하는 조합 문제이다.

조합 함수를 만들어서 중간 중간에 원소의 합을 더해주며

그 합과 S를 비교하며 카운트 해주면 된다.

#include <iostream>
#include <vector>
using namespace std;

int arr[21] = { 0 };
int cnt = 0, sum = 0, res = 0;

vector <int> v;
void combination(int N, int S) {
	if (cnt == N) return;
	else {
		for (int i = 0; i < N; i++) {
			if (v.empty() || v.back() < i) {
				v.push_back(i);
				sum += arr[i];
				cnt++;
				if (S == sum) res++;
				combination(N, S);
				v.pop_back();
				sum -= arr[i];
				cnt--;
			}
		}
	}
}

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

	for (int n = 0; n < N; n++) cin >> arr[n];

	combination(N, S);
	cout << res;

	return 0;
}