문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

문제 링크

풀이

크기가 양수이기 때문에 주어진 수열에서 아무것도 고르지 않는 경우는 제외한다.
모든 경우를 확인하며 그 부분 수열의 원소 합이 S가 되는 경우를 구하면 된다.

• N < 20 이기때문에 각 수열의 원소들이 부분수열에 포함되는 경우, 포함되지 않는 경우를 1과 0으로 구분하여 비트마스킹으로 해결할 수 있다.
• 혹은, dfs를 이용하여 해당 원소를 포함하고 다음으로 넘어가는 경우와 포함하지 않고 다음으로 넘어가는 경우를 구할 수 있다.

하지만 비트 마스킹으로 해결하는 경우 부분수열의 총 합을 구하기 위해 for문을 각 경우마다 주어진 수열의 크기만큼 돌아야 하는 비효율이 발생한다.
반면 DFS는 각 경우마다 이미 부분수열의 합을 구해두었기 때문에 부분수열의 합을 구하기 위한 반복을 할 필요가 없어 시간이 더 빠르다.

코드

중복순열

#include <iostream>
#include <vector>

using namespace std;

int n, s;
vector<int> seq;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int answer = 0;

    cin >> n >> s;
    seq.reserve(n);
    for (int i=0; i<n; i++){
        cin >> seq[i];
    }
    for (int i=1; i< (1<<n); i++){
        int number = 0;
        for(int j=0; j < n; j++){
            if ( i & 1<<j ) number += seq[j];
        }
        if (number == s) answer++;
    }

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

DFS

#include <iostream>
#include <vector>

using namespace std;

int n, s;
vector<int> seq;
int answer = 0;

void dfs(int depth, int sum){

    if ( depth == n ) return;
    if ( sum + seq[depth] == s ) answer++;

    dfs(depth+1, sum+seq[depth]);
    dfs(depth+1, sum);
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> s;
    seq.reserve(n);
    for (int i=0; i<n; i++){
        cin >> seq[i];
    }

    dfs(0, 0);
    
    cout << answer << "\n";
    return 0;
}