백준_1182_부분수열의 합

<비트마스크 풀이 방법>

 

for문의 i를 000~0001 부터 111~1111(1이 N-1 개)까지 증가시켜가면서, 모든 부분수열의 경우의 수에 대해 검사한다.

각 경우에 대해 for문의 j를 이용해 해당 비트가 1이면 그 원소를 더하고 0이면 더하지 않는다.

#include <iostream>
#include <vector>

using namespace std;

int N, S, x, cnt, sum;
vector<int> v;

void solve() {
	for (int i = 1; i < (1 << N); i++) { // i는 000~0001 부터 111~1111(1이 N-1 개)까지.
		sum = 0;
		for (int j = 0; j < N; j++) { // N개의 비트 읽기.
			if ((i & (1 << j)) != 0) 
				sum += v[j]; // 해당 비트가 1이면 그 원소를 부분수열에 추가.
		}
		if (sum == S) cnt++;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}
	solve();
	cout << cnt << '\n';
	return 0;
}

+ <재귀 풀이 방법>

부분수열에 포함시킬 수열 원소의 index를 1씩 증가시키면서 재귀 함수를 호출한다. 해당 원소를 부분수열에 포함시키는 경우(더하는 경우)와  포함시키지 않는 경우(안더하는 경우) 각각 재귀함수를 호출한다. index가 N이 되면 종료한다.

#include <iostream>
#include <vector>

using namespace std;

int N, S, x, cnt;
vector<int> v;

void solve(int index, int sum) {
	if (index == N) return;
	sum += v[index];
	if (sum == S) cnt++;
	solve(index + 1, sum - v[index]);
	solve(index + 1, sum);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}
	solve(0, 0);
	cout << cnt << '\n';
	return 0;
}