부분수열의 합(2)

문제

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

이전 글에서는 DFS 탐색을 통해 조합 알고리즘을 직접 구현헀다면, 이번에는 C++ STL 라이브러리에서 제공하는 next_permutation()을 통해 동일한 구현을 수행해본다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int n, s, temp, cnt;
vector<int> in_num;

void comb(int num) {

	int sum;
	vector<int> comb;

	for (int i = 0; i < n; i++) {
		if (i <= n - 1 - num) {
			comb.push_back(0);
		}

		else {
			comb.push_back(1);
		}
	}

	do {
		sum = 0;

		for (int i = 0; i < comb.size(); i++) {
			if (comb[i] == 1) {
				sum += in_num[i];
			}
		}

		if (sum == s) {
			cnt++;
		}

	} while (next_permutation(comb.begin(), comb.end()));
}


int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	cin >> n >> s;

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

	sort(in_num.begin(), in_num.end());

	for (int i = 1; i <= n; i++) {
		comb(i);
	}

	cout << cnt << "\n";
	return 0;
}