이번 문제를 처음에 접했을 때 부분 수열이 연속된 수들에서만 생성할 수 있다고 생각했다. 그래서 다음과 같이 풀었다.

• sum에 모든 배열의 값을 더한다.
• k를 1로 두고 배열의 n-1부터 0까지 검사하며 빼고 만약 S와 같으면 멈추고 cnt를 증가시키고 k도 증가시켰다.

그러나 이 문제에서 말하는 부분 수열은 기존 배열에서 연속하지 않아도 생성할 수 있는 문제였다. 예를 들어 배열의 인덱스 1을 더하지 않아도 인덱스 2는 더할 수 있다는 뜻이다. 그래서 깊이우선탐색을 활용했다.

• DFS의 인자는 인덱스를 나타내는 idx, 부분 수열의 합을 나타내는 sum, 부분 수열의 크기를 나타내는 size로 구성했다.
• idx가 n과 같아졌을 때 sum과 s가 같고, size가 0이 아니라면 구하고자 하는 부분 수열을 구한 것이므로 cnt를 증가시켜준다.
• DFS의 재귀호출은 두가지로 해주는데 DFS(idx+1, sum+arr[idx], size+1)은 배열의 다음 값을 더했을 때에 대한 DFS이고, DFS(idx+1, sum, size는 배열의 다음 값을 더하지 않았을 때에 대한 DFS이다.

Code

#include <iostream>
#define MAX 21
using namespace std;

int n, s;
int arr[MAX];
int cnt=0;
int sum=0;

void Input(){
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        sum+=arr[i];
    }
}

void DFS(int idx, int sum, int size){
    if(idx==n){
        if(sum==s&&size!=0){
            cnt++;
        }
        return;
    }
    DFS(idx+1, sum+arr[idx], size+1);
    DFS(idx+1, sum, size);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(0,0,0);
    cout<<cnt<<endl;
    return 0;
}