[BOJ / C++] 부분수열의 합 (백트래킹)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

void dfs(int depth, int sum, int& cnt, vector<int>& arr, int n, int s) {
	if (depth == n) {
		if (sum == s) {
			cnt++;
		}
		return;
	}

	dfs(depth+1, sum, cnt, arr, n, s);
	dfs(depth+1, sum + arr[depth], cnt, arr, n, s);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n, s;
	cin >> n >> s;
	vector<int> arr;
	for (int i = 0; i < n; i++) {
		int inp;
		cin >> inp;
		arr.push_back(inp);
	}

	int cnt = 0;
	dfs(0, 0, cnt, arr, n, s);

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

 

2. 분석

DFS 완전탐색 방법을 이용한다. 각 원소가 포함되거나, 포함되지 않거나 하는 경우를 모두 DFS로 탐색하고, depth == n이 되었을 때 sum == s인지 비교해서 골라낸다. 주의할 점은 s가 0일 때 모든 원소가 포함되지 않는 경우를 세게 되는데 해당 케이스에서만 1을 줄여주는 처리를 해주면 된다. Test Case에 s == 0인 경우가 나와있어 해당 부분을 확인할 수 있다.

 

 

3. 시간복잡도

각 깊이 노드에서 재귀 호출을 2번씩 진행하므로 depth가 n인 이진트리모양의 상태공간트리가 된다. 따라서 시간복잡도는 O(2^n)이 된다. 시간제한은 2초이고, n = 20 이하이므로, 2^20 = 1,048,576 (1M) < 10^9 이므로 통과할 수 있다.