6. DFS - 부분집합

 

1. 핵심 개념

값이 총 3개일 때, 트리 모양으로 가정합니다. D(1), D(2), D(3), D(4)가 있습니다. D() 안의 숫자는 level을 뜻합니다. D(1)은 0 0 0이고, D(2)는 첫째 값, D(3)는 둘째 값, D(4)는 셋째 값입니다. 루트부터 전위 순회를 하면서 왼쪽은 ch[level] = 1; 오른쪽은 ch[level] = 0; 입니다. level 1은 0 0 0입니다. level이 4일 때 부분집합을 출력합니다. 

 

void dfs(int level){
    
    if(level == N){
        if(!isEmpty()){
            for(int i=0; i<N; i++){
                if(ch[i] == 1)
                    sum += v[i];
            }
            if(sum == S)
                cnt++;
            sum = 0;
        }
        return;
    }
    
    ch[level] = 1;
    dfs(level+1);
    ch[level] = 0;
    dfs(level+1);
    
}

 

 

 

 

2. 백준 1182

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

#include <stdio.h>
#include <iostream>
#include <vector>
#define MAX_NUM 25
using namespace std;

int N, S;
int num;
int cnt = 0;
int ch[MAX_NUM];
vector<int> v;
int sum;

int isEmpty(){
    for(int i=0; i<N; i++){
        if(ch[i] == 1)
            return 0;
    }
    return 1;
}

void dfs(int level){
    
    if(level == N){
        if(!isEmpty()){
            for(int i=0; i<N; i++){
                if(ch[i] == 1)
                    sum += v[i];
            }
            if(sum == S)
                cnt++;
            sum = 0;
        }
        return;
    }
    
    ch[level] = 1;
    dfs(level+1);
    ch[level] = 0;
    dfs(level+1);
    
}

int main(void) {
    
    cin >> N >> S;
    
    for(int i=0; i<N; i++){
        cin >> num;
        v.push_back(num);
    }
    
    dfs(0);
    
    cout << cnt << endl;
    
    return 0;
}