[백준] 1182번: 부분수열의 합

Solved.ac 실버2
https://www.acmicpc.net/problem/1182

설명

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

입력

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

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

해결 Tip

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

• 재귀함수로 수열의 부분수열을 만들고, 그 부분수열을 더했을 때 합이 S인지 판별하면 끝
• 추가로 코드를 줄이기 위해서 부분수열을 만드는 과정과 더하는 과정을 합쳐서 처리

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAX_SIZE 20
using namespace std;

int N, S, ans;
int ary[MAX_SIZE+1];

void solve(int sum, int idx) {

    if (sum == S && idx != 1) ++ans;

    for (int i=idx ; i <= N ; i++) {
        sum += ary[i];
        solve(sum, i+1);
        sum -= ary[i];
    }
}

int main() {
    cin >> N >> S;
    for (int i=1 ; i <= N ; i++)
        cin >> ary[i];
    solve(0, 1);
    cout << ans;
    return 0;
}