[210616][백준/BOJ] 1182번 부분수열의 합

문제

입출력

풀이

완전탐색 문제이다.
부분수열의 합이 s와 같은 경우의 수를 찾는다.
cnt가 n과 같아지면 return을 한다.

-7, -3, -2, 5, 8의 경우에는 (-7)+(-3)+(-2)+5+8 = 1인 경우의 수 한개가 나온다.

코드

#include <bits/stdc++.h>
using namespace std;

int arr[22];
int n, s, ans = 0;

void d(int cnt, int idx)
{
	if (cnt == n) return;
	if (idx + arr[cnt] == s) ans++;

	d(cnt + 1, idx);
	d(cnt + 1, idx + arr[cnt]);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	d(0, 0);
	cout << ans;
}