[Brute Force - 재귀] 부분 수열의 합

예제 입력 1

5 0

-7 -3 -2 5 8

예제 출력 1

1

 

#include <stdio.h>
#define MAX_SIZE (21)

int N, S;
int num[MAX_SIZE];

int ans = 0;
int go(int* num, int start, int N, int nowSum, int S)
{
	// ★ 답을 찾았다고해서 반환해버리면 안된다.
	if (nowSum == S && start != 0) ans++;

	for (int i = start; i < N; i++)
	{
		go(num, i + 1, N, nowSum + num[i], S);
	}

	return ans;
}

int main(void)
{
	scanf("%d %d", &N, &S);

	for (int i = 0; i < N; i++)
		scanf("%d", &num[i]);

	printf("%d\n", go(num, 0, N, 0, S));

	return 0;
}

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

1182번: 부분수열의 합