[BOJ] 1182 - 부분수열의 합

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

---

[알고리즘풀이]

백트레킹을 이용해 만들 수 있는 모든 부분수열의 합을 구해본다.

#include<iostream>
#include<vector>

using namespace std;

int n_l[20], answer,n,m;

void bt(int i, int j, vector<int> v) {
	if (v.size() == i) {
		int temp = 0;
		for (int k = 0; k < i; k++){
			temp += v[k];
		}
		if (temp == m) {
			answer++;
		}
		return;
	}
	for (int k = j + 1; k < n; k++){
		v.push_back(n_l[k]);
		bt(i, k, v);
		v.pop_back();
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> n_l[i];
	for (int i = 1; i <= n; i++) {
		// i개 씩 뽑을거다.
		for (int j = 0; j < n + 1 - i; j++) {
			// j까지담김
			vector<int> v;
			v.push_back(n_l[j]);
			bt(i, j, v);
			v.pop_back();
		}
	}
	cout << answer;
}

---