백준 1182 부분수열의 합- 재귀 브루트포스 (c++)

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

1182번: 부분수열의 합

우선 수열의 길이가 최대 20이고, 합이 s가 되는 모든 경우를 찾아야 하므로

재귀함수를 이용한 브루트포스 방식으로 접근해보았다.

 

수열의 i번째 index를 탐색한다고 하면 그 이전 index는 탐색했다고 가정하고

그다음 인덱스 부터 나머지 모두를 전부 탐색하는 방식으로 재귀함수를 짜면 된다.

그리고 main함수에서는 0번째 index부터 탐색하면 된다.

그렇게 search하다가 합이 S가 되면 결과에 1을 더하면 된다.

#include <iostream>
using namespace std;
int N,S;
int arr[21];
int answer=0;
 
void search(int index,int sum){
    if(sum==S)
        answer++;
    for(int i=index; i<N; i++){
        search(i+1,sum+arr[i]);
    }
}
 
int main(void){
    cin>>N>>S;
    for(int i=0; i<N; i++)
        cin>>arr[i];
    search(0,0);
    if(S==0) answer--;
    cout<<answer;
}