백준 1182 부분집합의 합

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 어떤 원소들을 가지고 있는 집합이 있을 때 그 원소의 부분집합들 중 합이 S가 되는 것의 개수를 찾는 문제입니다.

 

원소의 개수가 20개 까지이므로 20개 일때의 부분집합의 개수는 2^20-1 입니다. 따라서 brute force로 해결이 가능하므로 

 

저는 그냥 함수를 하나 만들어서 재귀적으로 호출하며 모든 경우를 따지는 방법으로 풀었습니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int num;

void rec(int *arr,int N, int result, int S, int k) {
	if(result == S)
		num++;
	
	for(int i = k; i < N; i++) {
		rec(arr, N, result+arr[i], S, i+1);
	}
	
} 


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,S;
	cin >> N >> S;
	int arr[N];
	int result;
	
	for(int i = 0; i < N; i++)
		cin >> arr[i];
	
	for(int i = 0; i < N; i++) {
		result = arr[i];
		rec(arr, N, result, S, i+1);
	}
	
	cout << num;
	return 0;
}