부분수열의 합

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

1182번: 부분수열의 합

주어진 N개의 숫자 중 부분수열의 합이 S를 만족시키는 수열의 개수를 찾는 문제이다.

백트래킹을 이용해 모든 경우의 수의 수열을 뽑아낸뒤 그 수열의 합이 S를 만족시킨다면

카운트를 하는 방식으로 접근하였다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include<vector>
#include<algorithm>
#include <string>
#include<list>
#include<cmath>
#include<stack>
using namespace std;
#define MAX 21
int nu[MAX];
bool c[MAX];
int ans[MAX];
int n, s, a;
int idx;
vector <int> p;
int check(int idx, int cnt, int num) {
	int sum = 0;
	//num개를 다 뽑았다면 그 합을 구한후 S와 비교
	if (cnt == num) {
		for (int i = 1; i <= num; i++)
		{

			sum += ans[i - 1];

		}

		if (s == sum) {
			p.push_back(sum);
		}
		return 0;
	}
	//수열의 원소가 중복되지 않도록 저장
	for (int i = 0 + idx; i < n; i++) {
		if (!c[i] == true) {
			c[i] = true;
			ans[cnt] = nu[i];
			check(i + 1, cnt + 1, num);
			c[i] = false;
		}
	}
	return 0;


}
int main() {
	cin >> n >> s;
	//삽입
	for (int i = 0; i < n; i++) {
		cin >> nu[i];
	}
	//총 N개라면 1~N개를 뽑는 모든 경우의 수에 대해 백트래킹
	for (int i = 1; i <= n; i++) {
		check(0, 0, i);
	}
	cout << p.size();

}