부분수열의 합(1)

문제

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

해당 문제는 입력으로 주어진 n개의 숫자에서 1개 이상의 원소를 갖는 집합(부분수열)의 모든 성분 합이 S를 만족하는 경우를 출력하는 문제이다.

이를 위해 모든 경우를 탐색해야 하므로 가장 먼저 DFS 탐색 접근법을 생각했다.
하지만 단순히 DFS 탐색을 수행하면 시간복잡도가 O(N!)으로 말도 안되는 시간이 걸리므로, 연산 횟수를 줄이는 방법이 필요하다.

이를 위해 조합 알고리즘을 활용하여, DFS 순회 전에 정렬한 배열의 특징을 생각해서 이전 부모노드의 index+1 값을 DFS 함수의 인자로 받아 다음 레벨을 순회할 때마다 모든 숫자를 순회하지 않도록 했다.
추가로 DFS 함수의 인자로 sum을 넘겨주어, 매번 재귀 과정에서 각 부분수열 조합의 성분 합이 S를 만족하는지 확인하였다.

조합 알고리즘을 통해 완전탐색(브루트포스) 없이 매 level마다 문제의 조건을 만족하는 연산을 대폭 줄일 수 있다.
또한, 전체 시간복잡도는 처음의 O(N!)에서 O(2^N)으로 줄일 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int n, s, cnt, sum;
vector<int> in_num;

void DFS(int L, int start, int sum) {

	if (L == n) {
		return;
	}

	else {
		for (int i = start; i < in_num.size(); i++) {
			if (sum + in_num[i] == s) {
				cnt++;
			}

			DFS(L + 1, i + 1, sum + in_num[i]);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	int temp;

	cin >> n >> s;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		in_num.push_back(temp);
	}

	sort(in_num.begin(), in_num.end());

	DFS(0, 0, 0);
	
	cout << cnt << "\n";
	return 0;
}