# 백준 : 부분집합의 합(1182)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1182_sumofparts)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int N, S;
int cnt, sum;
long long int numbers[21];
int visit[21];

void DFS(int v) {
    if(v == N) return;
    if((sum + numbers[v]) == S) cnt++;
    DFS(v + 1); // not add
    sum += numbers[v];
    DFS(v + 1);
    sum -= numbers[v];
}

int main(void)
{
    cin>>N>>sum;
    for(int i=0; i<N; i++) cin>>numbers[i];
    DFS(0);
    cout<<cnt<<endl;
    return 0;
}

풀이

백트래킹이라는 기법에 대한 공부를 진행하고 있는데, 가장 기초적인 문제라고 해서 풀어보았다.
실제 DFS, BFS에 대한 개념이 바로 기억나지 않아서 좀 놀라긴 했는데..
덕분에 백트래킹 공부하면서 DFS, BFS 공부도 할 수 있어서 좋았다.
백트래킹은 DFS를 기반으로 해서 '모든 원소를 다 훑어보는' 일종의 브루트포스 형식을 의미한다.

몇가지 다른점을 이야기해보면

1. DFS에서 접점의 방문 유무를 확인하기 위해 사용하던 visit과 같은 내용을 사용하지 않는다
본 문제에서도 원하는 합의 유무를 확인하기 때문에, 합을 기준으로 접점 방문 유무를 따졌다.
2. 맨 마지막에 '접점을 방문하지 않은 척' 해야 한다.
사실 이부분이 제일 헷갈렸는데, 결국 검사할건 다 하고 검사하지 않은 척 해야한다는 말이다.
조금 유하게 표현하면, '다음 녀석들이 또 검사해볼 수 있도록 깨끗하게 정리하는 과정'이라고 보면 되겠다.
말은 이렇게 했지만 실제 코드 작성중에는 생각하지도 못했고, 또 참고사이트를 봐도 이부분을 이해하는게 어려웠다는...