[BOJ 1182] 부분수열의 합(비트마스크, 재귀함수, C++)

이 문제는 비트마스크와 재귀 함수로 풀 수 있다.

 

 

 

비트마스크로 문제를 풀어보았다.

 

 

 

재귀 함수로 풀 경우에는, 함수의 종료 조건을 논리적으로 구성해야 한다.

 

 

 

사실 비트마스크로 문제를 풀기 이전에, 재귀 함수로 문제를 풀었는데 종료조건이 틀렸었다.

 

 

 

합이 S일 때, Return하도록 구성했는데, 인덱스가 N일 때로 구성해야 문제가 없이 답을 구할 수 있다.

 

 

 

1. 비트마스크

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, S;
int arr[21];
int answer = 0;
int check[1024*1024];
 
void func(int idx, int sum, int visit){
    if(sum == S && visit != 0 && check[visit] == 0){
        check[visit] = 1;
        answer += 1;
    }
    
    if(idx < N){
        func(idx + 1, sum + arr[idx], visit | (1 << idx));
        func(idx + 1, sum, visit);
    }
    
    return;
}
 
int main() {
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        cin >> arr[i];        
    }
 
    func(0, 0, 0);
    memset(check, 0, sizeof(check));
    cout << answer << endl;
    return 0;
}

 

2. 재귀함수

#include <iostream>
using namespace std;
 
int N, S;
int arr[21];
int answer = 0;
 
void func(int idx, int cnt, int sum){
    if(idx == N){
        if(cnt != 0 && sum == S)
            answer += 1;
        return;
    }
    
    if(idx < N){
        func(idx + 1, cnt + 1, sum + arr[idx]);
        func(idx + 1, cnt, sum);
    }
    
    return;
}
 
int main() {
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        cin >> arr[i];        
    }
        
    func(0, 0, 0);
    cout << answer << endl;
    return 0;
}