[백준 1182번] 부분수열의 합 (C++)

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

1182번: 부분수열의 합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, S, result;
int arr[21];

void dfs(int idx, int sum)
{
    if(idx==N) return;
    if(sum + arr[idx] == S) result++; //누적합 + 현재값이 S면 카운팅

    dfs(idx+1, sum + arr[idx]); //현재 숫자 더하고 넘기기
    dfs(idx+1, sum); //그냥 넘기기
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> S;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    dfs(0, 0);
    cout << result;    
}

 

오랜만에 브루트포스 문제이다.

재귀를 사용하여 현재 숫자 값을 더하고 넘기기와 그냥 넘기기 2개를 돌려준다. (구간별 누적합 체크)

현재까지의 누적합 + 현재 값이 S가 된다면 정답을 추가해주고, idx==N이 되어 전부 탐색하면 종료해준다.