[BOJ] 백준 1182 부분수열의 합 c++ (dfs, 백트래킹, 브루트포스)

문제 출처 : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

dfs를 사용하여 해결한 문제이다.

 

현재 위치인 idx, 합을 나타내는 sum, 현재 수열 개수 cnt, 부분수열의 크기 size 를 넘겨주었고

 

size == cnt인 순간 합이 S인 경우를 체크하였다.

---

코드

#include <iostream>
#include <vector>

using namespace std;

int N, S;
int answer;

void dfs(vector<int> v, int idx, int sum, int cnt, int size){
    sum += v[idx];
    cnt++;

    if(size == cnt){
        if(sum == S) answer++;
        return;
    }

    for(int i = idx + 1; i < N; i++)
        dfs(v, i, sum, cnt, size);
    
    return;
}

int main(){
    cin >> N >> S;

    vector<int> v(N);

    for(int i = 0; i < N; i++){
        cin >> v[i];
    }

    for(int i = 1; i <= N; i++)
        for(int j = 0; j < N; j++)
            dfs(v, j, 0, 0, i);

    cout << answer;
}