백준 1182 (부분수열의 합) c++

문제

1182번: 부분수열의 합

수열의 갯수 n과 부분수열의 합 s가 주어지면 수열의 부분수열의 합이 s가 되는 경우의 수를 모두 구하는 문제입니다.

예를 들어 수열이 {-2, 5, -3} 인경우 부분수열의 갯수는 총 8개 입니다.

{-2}, {5}, {-3}, {-2, 5}, {-2, -3}, {5, -3}, {-2, 5, -3}, ⊙(공집합)

따라서 모든 부분집합에 대해서 각 부분집합의 합이 s와 같은지 보면 됩니다.

부분수열을 이루는 경우는

1) 수열의 수를 하나 선택해서 부분집합을 이룰지

2) 무시하고 다음으로 넘어갈지 선택해주면 됩니다.

이를 그림으로 표현하면 밑의 그림과 같습니다.

n=3이므로 idx가 3이 될때 모든 부분집합에 대해서 합들이 나타나게 됩니다. 

하지만 만약 s=0일때 공집합의 0까지 세게 되므로 마지막에 1을 뺴주어야 합니다.

위의 그림에서 보면 {-2, 5, -3} 입니다. 만약 s가 0이면 ⊙(공집합), {-2+5+(-3)} 2개이므로 1개를 뺴주어야합니다.

void recursion(int idx, int sum) {
	if (idx == n) {
		if (sum == s) cnt++;
		return;
	}

	recursion(idx + 1, sum);
	recursion(idx + 1, sum + arr[idx]);
}

idx는 부분수열의 인덱스 위치입니다. sum은 지금까지 더한 부분수열의 합입니다.

재귀함수가 2가지로 진행됩니다. 위에서 말했다 시피 

1) 그냥 무시하고 다음 인덱스로 넘어가기

2) 해당 인덱스의 수를 더하고 넘어가기

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
int s;
int cnt = 0;
int arr[21];
void recursion(int idx, int sum);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> s;

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

	recursion(0, 0);

	if (s == 0)cnt--;
	cout << cnt;


	return 0;
}
void recursion(int idx, int sum) {
	if (idx == n) {
		if (sum == s) cnt++;
		return;
	}

	recursion(idx + 1, sum);
	recursion(idx + 1, sum + arr[idx]);
}