C++ SWEA 2817. 부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=3

SW Expert Academy

풀이

정렬 후에 자연수를 더한다. / 더하지 않는다. 두 가지로 나누어 계산한다. DFS방식으로 계산한 후에 부분 수열의 합보다 작으면 계속, 부분 수열의 합이 된다면 +1, 부분수열보다 크면 break로 진행한다.

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int ans = 0; // 정답
int N, A; // N개의 자연수, A : 합
vector <int> v;
void dfs(int num, int s_sum) {

	if (s_sum == A) { // 부분 수열의 합
		ans++;
		return;
	}
	else if (num >= v.size() - 1 || s_sum > A) { // 부분수열의 합을 넘거나 인덱스 오버
		return;
	}
	else {
		dfs(num+1, s_sum); // i번째 원소를 더 하지 않았을 경우
;		s_sum += v[num+1];
		dfs(num+1, s_sum); // i번째 원소를 더했을 경우
	}

}

int main() {
	int t_c = 0;
	cin >> t_c;

	for (int i = 0; i < t_c; i++) {
		cin >> N >> A;

		for (int i = 0; i < N; i++) { // 대입
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}

		sort(v.begin(), v.end()); // 정렬
		dfs(0, 0); // 0번 요소 더하지 않았을 경우 
		dfs(0, v[0]); // 0번 요소 더했을 경우 
		cout<<"#"<<i+1<<" " << ans << endl;
		
		// 초기화
		v.clear();
		ans = 0;
	} // t_c
	return 0;
}