[BJ] 1182번 : 부분수열의 합(재귀,DFS) /c++ & c / 제한시간 : 2초

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;

int ch[20];
int num[20];
int n, s, cnt = 0;

void partition(int level) {
	int i, temp = 0, check = 0;
	if (level == n) {
		for (i = 0; i < level; i++) {
			if (ch[i] == 1) {
				temp += num[i];
			}
			else check++;
		}
		if (check == level) return;
		if (temp == s)cnt++;
		return;
	}
	else {
		ch[level] = 1;
		partition(level + 1);
		ch[level] = 0;
		partition(level + 1);
	}
}

int main() {
	int i;
	scanf("%d %d", &n, &s);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	partition(0);
	printf("%d\n", cnt);
	return 0;
}

 

각 레벨마다 num[level]값의 ch를 하나는 '1'로 나머지는 '0'으로 저장한다.

 

level == n 이 되었을때 ch[ ]값이 1인 것들만 temp에 더해주면

 

수열의 부분집합으로 표시할 수 있다. 결과값이 s와 같다면 cnt++

 

partition 함수에서 check는 공집합을 뜻한다. 즉, 모든 원소, num[ ],들의 ch 값이 0인것들은 cnt하기 직전에 return을 시켜준다.

 

.

 

이진트리 레벨 탐색의 개념을 사용함