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

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

1182번: 부분수열의 합

전에 재귀로 풀었던 문제인데 가볍게 비트마스킹 연습할 겸 다시 풀어보았다.

근데 이 문제는 재귀로 푸는게 더 빠르네..ㅋㅋㅋㅋㅋㅋㅋㅋ

 

#include <iostream>
using namespace std;

int n, s;
int arr[20];
int cnt = 0;

void calc(int i, int sum) {
	if (i == n) {
		if (sum == s) cnt++;
	}
	else {
		calc(i + 1, sum);  //arr[i] 안 더하는 경우
		calc(i + 1, sum + arr[i]);  //arr[i] 더하는 경우
	}
}

int main() {

	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	calc(0, 0);

	if (s == 0) cnt--;

	cout << cnt;
}

이건 재귀로 푼거

 

 

#include <iostream>

using namespace std;

int main() {
	int n, s;
	int arr[20];
	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];

	int cnt = 0;

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

	cout << cnt;
}

 

비트마스킹으로 푼거