[백준 1182] 부분수열의 합 cpp

문제
N개의 정수로 이루어진 수열이 있을 때, 부분수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하라.

입력
첫째 줄에 정수의 개수 N(1이상 20이하)과 S(절댓값 백만)를 입력
둘째 줄에 N개의 정수를 입력하며 각 정수는 절댓값 십만을 넘지 않는다.

출력
합이 S가 되는 부분수열의 개수를 출력

---

모든 부분수열의 합을 탐색해야 한다. 따라서 모든 부분수열을 생성할 수 있는 방법을 생각해봐야 한다.

나는 1부터 N개를 포함한 부분수열이 존재하기 때문에 부분수열의 개수에 따라 부분수열을 생성하도록 하였다.

이후 해당 개수를 갖는 부분수열의 합을 백트래킹으로 구하여 S와 맞는지 검사하였다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

int Numbers[20];
int N, S;
int answer;

void solution(int next, int total,int picked, int topick) {
	// 모두 선택했다면 합과 S를 비교한다.
	if (topick == picked) {
		if (total == S)
			answer++;
		return;
	}
	// 백트래킹으로 부분수열의 합을 구한다.
	for (int i = next; i < N; i++) {
		total += Numbers[i];
		solution(i + 1, total, picked + 1, topick);
		total -= Numbers[i];
	}
}
int main()
{
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> Numbers[i];
	}
	
    //i개의 정수를 갖는 부분수열
	for (int i = 1; i < N + 1; i++) {
		solution(0, 0, 0, i);
	}

	cout << answer << endl;
	return 0;
}