[백준] 1182 부분 수열의 합

[백준 1182]부분수열의 합

재귀를 이용해 해결하였다.
모든 가능한 부분 수열을 구해 합과 같으면 카운트를 올렸다.

C++ 코드

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

int N, S;
int num[20];
int count_ = 0;

void fun(int n, int pre_sum) {

	if (n == N) {
		if (pre_sum == S)
			count_++;

		return;
	}

	//포함
	fun(n + 1, pre_sum + num[n]);
	//미포함
	fun(n + 1, pre_sum);


}

int main() {

	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	fun(0, 0);
	if (S == 0) count_--;
	cout << count_ << endl;

	return 0;
}

아래 방법은 비트마스크를 사용한 방법이다.
부분집합을 '하나의 수'로 나타내는 개념인데,
만약 {1,2,3,4,5} 라는 집합이 있을때 {1,2,4} 라는 부분집합은 01011 로 표시할 수 있다.
공집합은 포함되지 않으므로,
00001 (원소 1만 포함) 부터 11111 까지 증가하는 과정에서 모든 경우의 부분집합을 구할 수 있다.

#include <iostream>
using namespace std;

int main() {

	int N, S;
	cin >> N >> S;
	int num[20];
	int count_ = 0;

	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	// {0 0 0 0 0}
	// 0 0 0 0 1 
	// 1 1 1 1 1 = 31 // 100000 -> 32

	for (int i = 1; i < (1 << N); i++) {
		int sum = 0;
		for (int k = 0; k < N; k++) {
			if (i & (1<<k)) {
				sum += num[k];
			}
		}
		if (sum == S)
			count_++;
	}
	cout << count_ << endl;
	return 0;
}