[C++] 백준 1182번? : 부분수열의 합

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

1182번: 부분수열의 합

dfs를 이용해 풀었다.

주어진 예제의 경우 2^5만큼 연산되는거라 빠르진 않아서 시간 제한이 넉넉한건가

 

n의 최대가 20이니까 최악인 경우 2^20이겠지만, 연산 중에 원하는 s와 같은게 나오면 더 이상 탐색하지 않아도 되기 때문에 수행시간은 2^20에 해당하는 만큼은 안나오겠죠?

이걸 고려해주면 백트래킹이라 말할 수 있을 것같다.

 

그치만 내 코드가 백트래킹을 고려해서 쓰여진건 아닌것같은데..

뭔가 else가 있어야하지 않을까

뭔가 풀리긴 했는데, 백트래킹은 구현 못한거 같아서 좀 아쉽다

 

 

#include <iostream>
#include <stack>
#include <vector>
#include<algorithm>


using namespace std;

int n, s; 
int *rawDataArr;
vector<int> graph;
int cnt = 0;

void dfs(int x, int rst) {
	if(s == rst && x < n) {
	
		cnt++;
	}
	

	for (int i = x+1; i < n; i++) {
		dfs(i,rst+graph[i]);
	}
	
	
	
	
}

int main() {
	cin >> n >> s;
		
	rawDataArr = new int[n];
	int curr;
	
	for (int i = 0; i < n; i++) {
		cin >> curr;
		graph.push_back(curr);
	}
	
	for (int i = 0; i < graph.size(); i++) {

			
   		dfs(i, graph[i]);
	}
	
	
	cout << cnt;
	
	
	return 0;
}