[C++] BOJ 1182 - 부분집합의 합

#include <iostream>
#include <vector>

using namespace std;

int a[20];
int n,s;
int cnt = 0;
vector<int> v;

void cnt_case(int n, int r, int index) {
	
	if(r == 0) {
		int sum = 0;
		for(int i=0;i<v.size();i++) 
			sum += v.at(i);
			
		if(sum == s) cnt++;
		return;
	} 


	if(n == r) {
		int sum = 0;
		
		for(int i=0;i<n;i++) 
			v.push_back(a[i+index]);
		
		for(int i=0;i<v.size();i++) 
			sum += v.at(i);
			
		if(sum == s) cnt++;
		
		for(int i=0;i<n;i++) 
			v.pop_back();
		
		return;
	} 
	
	v.push_back(a[index]);
	cnt_case(n-1,r-1,index+1);
	v.pop_back();
	cnt_case(n-1,r,index+1);

}


int main() {
	scanf("%d %d",&n,&s);
	
	for(int i=0;i<n;i++) 
		scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++) {
		cnt_case(n,i,0);
	}
	
	printf("%d",cnt);
}

조합(comb)를 사용해서 풀었습니다(조합 알고리즘 : http://2nners-computer.tistory.com/21?category=756885)

nC1 부터 nCn까지의 부분집합들을 조합으로 꺼내 vector에 집어넣은 후 그 합을 s와 비교하는 원리입니다 :)