백준 1182번 C++

백준 1182번 부분수열의 합
https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
using namespace std;
int arr[30];
int n,m,cnt1;
void func(int cur,int sum) {
	if (cur == n) {
		if (sum == m)
			cnt1++;
		return;
	}
	func(cur + 1, sum);
	func(cur + 1, sum + arr[cur]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n>>m;
	for (int x = 0; x < n; x++)
		cin >> arr[x];
	func(0,0);
	if (m == 0)
		cnt1--;
	cout << cnt1;
}

문제 풀이
재귀함수를 이용해서 푸는 문제입니다. func()이라는 함수를 만들어서 반복적으로 호출하면 됩니다. 문제 조건에 맞게 sum==n이 되는 경우에는 전역변수 cnt값을 ++해주시고 함수를 return시킵니다. sum!=n일 때
func(cur + 1, sum), func(cur + 1, sum +arr[cur])
두 문장을 선언해줍니다. sum은 총합이고 sum+arr[cur]은 sum에 그 다음 인덱스값을 더한다고 생각하시면 됩니다. 이런 식으로 반복하게 되면 부분수열의 개수를 구할 수 있습니다. 재귀 함수가 두 줄에서 모두 호출하는 코드 같은 경우에는 직접 손으로 그리셔서 풀면 이해하는데 더 도움이 될 것 같습니다.