뚝딱뚝딱

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

💡 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

[출력]
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

부분수열의 개념을 정확히 몰라서 처음에는 연속적인 수열을 생각했는데, 그냥 수열 내 부분집합이라 생각하면 된다.

단, 공집합은 제외한다.

✅ 문제 풀이

• 처음에는 visited 배열을 선언하고 방문 여부를 바꾸면서 백트래킹으로 해결하려했으나, 코드가 복잡하고 한눈에 안들어와서 매우 간단한 재귀함수 풀이로 바꾸었다.
• func(num, sum)라는 함수를 사용할 건데, num은 현재 수열에서 몇개까지 봤는지이고, sum은 수열에서 num번째 수를 포함하거나 포함하지 않은 값이다. 즉 누적 합이다.
• func()함수 내에서 만약 num이 N이면, 즉 끝까지 다 방문했을경우에, sum이 S와 같으면 answer를 하나 올려준다. 그리고 return을 통해 더이상 재귀가 일어나지 않도록 한다.
• 그리고 다음 값을 더하지 않는 경우 func(num+1, sum)와 다음 값을 더하는 경우 func(num+1, sum+arr[num])로 두번 호출하여 재귀를 이어나가도록 한다.
• 그림으로 나타내면 다음과 같다. 그림에서는 예제의 값으로 사용하였다.

수열의 num번째 값을 더한 쪽을 왼쪽, 안더한 쪽을 오른쪽으로 하여 가지치기 형태로 재귀를 호출하게 된다.

보면 맨 오른쪽의 아무것도 더하지 않는 공집합이 포함되어 있음을 알 수 있다.

• num은 0, sum은 0부터 시작한다. 
• func(0,0)을 하고 나면 count 된 값이 answer가 된다.
• 주의할 점은, S가 0인 경우에, 공집합의 0도 count에 포함시켜버리므로, 이런 경우에는 answer를 하나 빼주면 된다. 

✏ 코드 전문

#include<iostream>

using namespace std;

int N, S, answer=0;
int *arr;

void func(int num, int sum) {
	if (num == N) {
		if (sum == S) {
			answer++;
		}
		return;
	}
	func(num + 1, sum);
	func(num + 1, sum + arr[num]);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;

	arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	
	func(0, 0);

	if (S == 0) answer--;

	cout << answer;

	return 0;
}