[백준/BOJ] 백준 1182번 : 부분수열의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

부분 수열을 만드는 과정 중에 크기가 양수인 부분수열이 만들어졌을 때 수열의 원소들의 합이 s인 부분수열의 개수를 센다. 부분 수열을 만들 때는 중복된 부분수열을 만들지 않기 위해 이전에 고른 위치보다 큰 위치에서 숫자를 고른다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, s;
vector<int> number;
int result = 0;

void Solve(int last_selected, vector<int>& selected)
{
	//크기가 양수인 부분수열이 만들어 졌을때
	if (selected.size() != 0)
	{
		int sum = 0;

		for (int i = 0; i < selected.size(); i++)
		{
			sum += selected[i];
		}

		//수열의 원소들의 합이 s일때
		if (sum == s)
			result++;
	}

	//부분수열을 만든다 
	//중복된 부분수열을 만들지 않기 위해 이전에 고른 위치 보다 큰 위치에서 숫자를 고른다
	for (int i = last_selected + 1; i < n; i++)
	{
		selected.push_back(number[i]);

		Solve(i, selected);

		selected.pop_back();
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;

	cin >> n >> s;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		number.push_back(input);
	}

	vector<int> selected;
	Solve(-1, selected);

	cout << result;

	return 0;
}