BOJ [1182] 부분집합의 합

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

1. 분류

브루트 포스, 비트마스크

2. 풀이

N개의 원소를 갖는 집합에서 합이 S인 부분집합의 개수를 세는 문제.

부분집합은 2^N개만큼 존재한다.

부분집합을 구하는 방법은 여러 가지가 있겠지만 나는 비트연산을 이용했다.

A, B, C를 갖는 집합의 부분집합을 표로 그려보면 다음과 같다.

정수	이진수	부분집합
0	000
1	001	A
2	010	B
3	011	A B
4	100	C
5	101	A C
6	110	B C
7	111	A B C

위 사실만 알면 부분집합을 구하는 건 다 한 것이다.

정수 0부터 2^N - 1까지 반복문, 그 안에 원소의 개수(N)개만큼 도는 반복문.

그리고 반복문 두 개의 인덱스를 AND연산하면 부분집합을 구해낼 수 있다.

3. 소스코드

#include <cstdio>

int main()
{
	int n, s, cnt = 0, a[25] = { 0 };
	scanf("%d %d", &n, &s);

	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i < (1 << n); i++)
	{
		int sum = 0;

		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
				sum += a[j];
		}
		
		if (sum == s)
			cnt++;
	}

	printf("%d\n", cnt);

	return 0;
}