1182 부분수열의 합

1182 부분수열의 합

정신줄 놓을것같은 백트래킹의 시작

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

1. 문제

---

간단 설명

N개의 원소를 입력 받고,

이 수열의 부분수열의 합이 S가 되는 경우의 수를 구하는 문제

간단한 문제인줄 알고 도전했다가 엄청 헤맸다

2. 문제 분석

---

알고리즘

크게 두가지 접근법

1. 조합을 통해 부분수열을 직접 생성하거나
2. 각 원소를 넣을지 말지 따지는 방법

여기선 2번이 더 쉬울것 같아 2번으로 접근했다

1. 입력받기 
2. 레벨 0, 총합 0을 매개변수로 가지는 DFS함수를 호출하여 재귀를 시작한다
    2-1. 현재 레벨이 원소 개수만큼 도달했는지 체크
        - 즉, 1번 원소, 2번 원소 , ... , N-1번째 원소, N번째 원소까지 다 골라야 재귀가 종료된다
    2-2. 매개변수로 받은 sum값과 현재 원소를 더하면 목표값인 S가 되는지 체크한다
        - 여기서 `return` 하지 않는게 중요하다.
    2-3. 레벨을 1 증가시키고, 총합에 현재 원소를 더하는 sum을 매개변수로 가지는 DFS호출
    2-4. 레벨을 1 증가시키고, 총합을 현재 원소를 더하지 않는 sum을 매개변수로 가지는 DFS호출
        - 즉, 더하고 가냐 그냥 가냐 분기를 나누는 것

필요변수

원소 개수 N, 목표값 S

원소를 담을 배열 arr, 경우의수를 체크할 cnt

현재 레벨과 총합을 매개변수로 갖는 DFS() 함수

주의점

• 언제 재귀함수에서 return할 것인지 타이밍 잘 잡을 것
• {0, 0} 원소에서 0을 만드는 괴상한 반례도 있으므로 주의할 것 (답은 3가지임)

3. 소스코드

---

#include <iostream>

using namespace std;

int N, S;
int arr[21];
int cnt = 0;

void DFS(int level, int sum) {

	if (level == N) return; // 가지치기 조건 1. N을 모두 더한 경우
	if (sum + arr[level] == S) { // 
		cnt++;
	}

	DFS(level + 1, sum + arr[level]);
	DFS(level + 1, sum);

}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> S;

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

	DFS(0, 0);

	cout << cnt;

	return 0;
}