[알고리즘] c++ cpp 부분수열의 합

포인트

1. 부분 수열의 합을 구하는 방법? (조합적인 방법, 비트마스크 방법)

2. 이번에는 비트마스크로 푸는 방법을 알아보자

비트마스크로 푸는 이유는 조금더 빠르고 간단한게 풀기 위해서 이다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

비트 마스크로 구하는 방법

#include <iostream>
#include <vector>

using namespace std;
vector<int> a;
int main () {
    int n, m;
    cin >> n >> m;
    a.resize (n);

    for (int i=0; i < n; i++) { //자릿수 마다 입력을 한다. 
        cin >> a[i];
    }

    int answer=0;

    for (int i=1; i < (1 << n); i++) { //00000 인 상황을 제회 (00001, 00010, 00011, 11111)까지 
        int sum=0; 
        for (int k=0; k < n; k++) {//(자릿수 마다)
            if (i & (1 << k)) sum+=a[k]; //자릿수마다 1이 있는지를 조회 한다.
        }
        if (sum == m) answer+=1;
    }

    cout << answer << '\n';
    return 0;
}

재귀로 구하는 방법

#include <iostream>

using namespace std;
int map[20];
int n, m;
int ans = 0;

void go(int index, int sum) {
    if (index == n) {
        if (sum == m) {
            ans += 1;
        }
        return;
    }

    go(index + 1, sum + map[index]); // 부분수열을 더한다.
    go(index + 1, sum); // 부분수열을 더하지 않는다.
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    } //input

    go(0, 0);
    if (m == 0) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}