백준(BOJ) 1182번 부분수열의 합

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

문제

N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

코드 ( C++)

#include <iostream>

using namespace std;

int N, S;

const int MAX = 20;

int arr[MAX];

int cnt;

void find(int sum, int n)

{

if (n == N) {   // n이 N이 된다면 S와 같은지 보고 같다면 cnt 를 1 더해준다.

if (sum == S)

cnt++;

return;

}

find(sum + arr[n], n + 1); // 숫자를 더해주고 n을 1 늘린다.

find(sum, n + 1); // 숫자를 더하지 않고 n을 1늘린다.

}

int main()

{

cin >> N >> S;

for (int i = 0; i < N; ++i)

{

cin >> arr[i];

}

find(0, 0);

if (S == 0) // S가 0일시 끝까지 아무것도 더하지않아도 경우의수가 추가 되기 때문에 1을 빼줬다.

cout << cnt - 1 << endl;

else

cout << cnt << endl;

return 0;

}