[BOJ/C++] 부분 수열의 합(1182번)

1. 개요

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

1182번: 부분수열의 합

1-1. 설명

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

1-2. 제한 사항

 - 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어지며, N은 1 이상 20 이하, S의 절댓값은 1,000,000을 넘지 않음

 - 둘째 줄에 N개의 정수가 빈칸을 사이에 두고 주어지며, 주어지는 정수의 절댓값은 100,000을 넘지 않음

---

2. 구현

2-1. 풀이

재귀를 이용하여 완전 탐색 알고리즘을 사용하였다. 주어지는 N이 적어 완전 탐색을 사용해도 충분히 풀어 나갈 수 있었다. 

2-2. 코드 

#include <iostream>
using namespace std;

int arrays[20];
int result, N, S;

void recursive(int sum, int index);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S;
    for (int i = 0; i < N; i++) cin >> arrays[i];

    result = 0;
    recursive(0, 0);
    if (S == 0) result -= 1; // 공집합 제외
    cout << result << "\n";
    return 0;
}

void recursive(int sum, int index) {
    if (sum == S) result += 1;
    for (int i = index; i < N; i++) recursive(sum + arrays[i], i + 1);
}