백준 1182 부분 수열의 합 [BruteForce]

문제 링크: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제 풀이

예를 들어 {1, 2}의 부분 수열은 다음과 같다.

공집합, {1} , {2} , {1, 2} = 4개(2^2)

 

이러한 부분 수열들을 다 만들려면, 해당 숫자를 포함을 시킬지 안 할지를 결정해서 더 해주면 된다.

 

주의할 점이, 공집합은 0이랑 결과값이 같기 때문에 만약에 s가 0이라면 -1을 해줘야 한다.

이는 모든 수열에서 해당 숫자를 포함하지 않았을 때가 포함되기 때문이다.

그리고 중간에 정답을 찾은 경우에도 계속 진행해야 올바른 답을 찾을 수 있다.

{-2, 2, 0}의 경우 정답은 {0}, {-2, 2}, {-2, 2, 0}이 될 수 있기 때문이다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

// 각 원소를 포함시킬지 말지를 다 시도해본다.

int ans;

void solve(vector<int>& v, int idx, int sum, int s)
{
	// 정답인 경우
	if (sum == s && idx == v.size())
	{
		ans++;
		return;
	}

	// 불가능한 경우
	if (idx >= v.size()) return;

	// idx에서 숫자를 선택하는 경우
	solve(v, idx + 1, sum + v[idx], s);
	// idx에서 숫자를 선택하지 않는 경우
	solve(v, idx + 1, sum, s);
}

int main()
{
	freopen("input.txt", "r", stdin);
	int n, s;
	cin >> n >> s;
	vector<int> v(n, 0);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	solve(v, 0, 0, s);

	if (s == 0) cout << ans - 1;
	else cout << ans;
	return 0;
}