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

#include <iostream>
using namespace std;
 
int n, s, sum, counted;
int arr[21];
bool visited[21];
 
void dfs (int start)
{
    visited[start] = true;
    int cur = start;
    sum += arr[start];
 
    if (sum == s)
    {
        counted++;
    }
 
    for (int i = start + 1; i < n; i++)
    {
        int next = i;
 
        if (visited[next] == false)
        {
            dfs(next);
            sum -= arr[next];
            visited[next] = false;
        }
    }
}
 
int main(void)
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    for (int i = 0; i < n; i++)
    {
        dfs(i);
        visited[i] = false;
        sum -= arr[i];
    }
 
    cout << counted;
}

 

브루트포스로도 할 수 있고, dfs나 bfs로도 할 수 있고, 백 트래킹으로도 할 수 있겠다.

사실 이 모든 게 전체 탐색을 어떤 순서, 또는 어떤 방식으로 진행하느냐의 차이밖에 없으니.