BOJ 1182 부분집합의 합

문제출처 : https://www.acmicpc.net/problem/1182

1. 문제요약

- 집합, N개의 원소, 부분집합의 합이 S를 만족시키는 경우의 수

- N < 20, lSl < 1,000,000, l원소l < 100,000

- 공집합은 제외

2. 접근방법

- 부분집합의 개수는 2^N = 2^20 ≒ 1억번 ≒ 1초

- 모든 부분집합의 합을 다 구해보면 된다.

3. 시간복잡도

- 재귀 : 2^N => 테스트 결과 4ms

- Bit Mask : 2^N * N => 테스트 결과 52ms

4. 회고

- 재귀로 구현했을 때

  : 공집합인지 확인하는 과정이 필요함. S의 값이 0인 경우 공집합의 합은 0 이므로

  : 처음에는 선택한 원소의 개수도 재귀로 넘겼는데 S가 0이 아닌 경우는 공집합을 포함해도 경우의 수에 포함 되지 않으므로 

   마지막에 계산할 때, S가 0인 경우 1가지 경우의 수를 빼주면 됨.

- Bit Mask로 구현했을 때

  : 좀 더 구현에 연습이 필요함

재귀 소스코드

#include<iostream>
using namespace std;

int n, s, cnt = 0;
int v[21];

void dfs(int pos, int sum){
	if (pos == n){
		if(sum == s)
			cnt++;
		return;
	}
	dfs(pos + 1, sum + v[pos]);
	dfs(pos + 1, sum);
	return;
}

int main(void){
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	dfs(0, 0);
    if(s == 0) cnt--;
	cout << cnt << "\n";
	return 0;
}

Bit Mask 소스코드

#include<iostream>
using namespace std;

int n, s, ans;
int v[21];

int main(void){
	freopen("Text.txt", "r", stdin);
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> v[i];

	// 공집합을 제외한 모든 부분집합(000...001 ~ 111...111)
	for (int i = 1; i < (1 << n); i++){
		int sum = 0;
		// 하나의 부분집합에서 각 원소가 부분집합에 속하는지 확인
		for (int j = 0; j < n; j++)
			if ((1 << j) & i)
				sum += v[j];

		if (sum == s)
			ans++;
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]