[BOJ1182][C++] 부분수열의 합

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

1182번: 부분수열의 합

 

문제

 

해결

원소를 차례로 돌면서 현재의 값을 더하거나, 더하지 않고 여태까지의 원소의 합을 구하면 모든 부분수열의 합을 구할 수 있다. 그 중에서 입력한 값과 동일한 값을 가진 부분수열의 개수를 구하면 된다.

🎈Key Point🎈

백트래킹

 

[전체 코드]

#include <iostream>
using namespace std;

int n, s;
int arr[20];
int result = 0;

void func(int cur, int total) {
	if (cur == n) {
		if (total == s) result++;
		return;
	}

	// 현재 가리키는 값을 더하거나 / 안 더하거나
	func(cur + 1, total);
	func(cur + 1, total + arr[cur]);
}

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

	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];

	func(0, 0);
	if (s == 0) result--;	// 공집합일 때
	cout << result;
}