백준 / 1182 부분수열의 합 C++

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

백트래킹 문제이지만 백트래킹으로 안 풀고 브루트포스로 풀었다. (너무 잠이 와서 생각을 멈췄다.)

n개의 수가 입력 받으면 그 수의 부분 수열의 합이 주어진 s와 같은게 몇 개나 있는지 구하는 문제이다.

문제 자체는 어렵지 않지만, 백트래킹이 더 코드도 깔끔하고 시간도 줄어서 내일 풀어보려 한다.

 

브루트포스는 다음과 같이 하면 된다.

n=10이라 예를 들면 10으로 만들 수 있는 index의 조합을 모두 구한다. (ex) 10C1, 10C2, ..., 10C10

그리고 해당 index의 배열 값을 더해서 s와 같은지 확인하면 된다.

 

코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, s;
vector<int>v;
vector<vector<int>>combination;

void make_combination(int n, int r)
{
	combination.clear();
	vector<int>com;

	vector<int>vec;
	for (int i = 0; i < n; i++) {
		vec.push_back(i);
	}
	vector<int>idx;
	for (int i = 0; i < r; i++) {
		idx.push_back(1);
	}
	for (int i = 0; i < (n - r); i++) {
		idx.push_back(0);
	}
	sort(idx.begin(), idx.end());

	do {
		for (int i = 0; i < n; i++) {
			if (idx[i] == 1) {
				com.push_back(vec[i]);
			}
		}
		combination.push_back(com);
		com.clear();
	} while (next_permutation(idx.begin(), idx.end()));
}

int main()
{
	int res = 0;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	int tmp_sum;
	for (int i = 1; i <= n; i++) {
		combination.clear();
		make_combination(n, i);

		for (int j = 0; j < combination.size(); j++) {
			tmp_sum = 0;
			for (int k = 0; k < combination[j].size(); k++) {
				tmp_sum += v[combination[j][k]];
			}
			if (tmp_sum == s)
				res++;
		}
	}

	cout << res;
}