[백준 1182번] 부분수열의 합 (C++)

PS/백준 알고리즘[BOJ]

[백준 1182번] 부분수열의 합 (C++)

BE_개발자 2023. 10. 30. 20:21

728x90

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

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

#include<iostream>

using namespace std;
int seq[20];
int N, S, ans;

void func(int cur, int cnt, int sum) {
	if (cur == N) {
		if (sum == S && cnt != 0) ans++;
		return;
	}
	//다음 원소를 포함한 경우와 포함하지 않은 경우로 나누기
	func(cur + 1, cnt, sum);
	func(cur + 1, cnt + 1, sum + seq[cur]);
}


int main(void) {
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> seq[i];
	func(0, 0, 0);
	cout << ans;

	return 0;
}

728x90