[BOJ]1182번: 부분수열의 합

내가 처음에 생각한 방법

//2023-08-26.
#include "bits/stdc++.h"

using namespace std;
int n, s, cnt;
int v[21];  //주어진 수열 저장
bool isUsed[21];
int arr[21];    //부분수열 저장
void func(int k, int f) {   //k=현재 부분수열의 크기+1
    if (k == f) {
        int sum = 0;
        for (int i = 0; i < f; i++)
            sum += arr[i];
        if (sum == s) {
            cnt++;           
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (k == 0 || (arr[k - 1] <= v[i] && !isUsed[i])) {
            arr[k] = v[i];
            isUsed[i] = 1;
            func(k + 1, f);
            isUsed[i] = 0;
        }
    }
}

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

    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    for (int i = 1; i <= n; i++)
        func(0, i);
    cout << cnt;
}

○ func(0, 1), func(0,2), ····,func(0,n) : 각각 크기가 k인 부분수열 

 

이런 식으로 코드를 짜도 모든 부분수열의 개수를 찾을 수 있고, 수열의 합이 s가 되는 부분수열의 개수를 구할 수 있다.

하지만 결과는

 

안 그래도 시간복잡도가 큰 백트래킹 방법을 쓰는데 이걸 n번 for문을 도니 시간 초과가 날 수밖에 없다. 

다른 방법으로 부분 수열에 접근해야 한다.

---

그 방법은 수열의 k번째 원소를 부분수열에 포함시킬지 말지 결정하는 것이다.

부분수열의 합을 기준으로 상태 트리를 그려보자.

맨 처음에는 부분수열에 어떤 원소도 포함되지 않아 0이다.

k번째 원소가 포함되지 않으면 왼쪽으로 가지가 뻗고, 포함되면 오른쪽으로 가지를 뻗는다.

첫 번재 원소인 -4를 포함하지 않으므로 0이 된다.

두 번째 원소인 6도 포함하지 않으므로 0이 된다.

마지막 원소인 8도 포함하지 않아 0이다.

모든 원소가 포함되지 않은 공집합을 찾았다.

다시 위로 올라가서 이번에는 8을 포함한다. 상태 트리에 8이 추가된다.

이런 과정을 반복하면 모든 부분 수열의 합을 구할 수 있다.

//2023-08-26.
#include "bits/stdc++.h"

using namespace std;
int n, s, cnt;
int v[21];

void func(int cur, int tot) {
    if (cur == n) {
        if (tot == s) cnt++;
        return;
    }
    func(cur + 1, tot);	//cur번째 원소 추가x
    func(cur + 1, tot + v[cur]);	//cur번째 원소 추가
}

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

    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    func(0, 0);
    if(s==0){   //s==0인 경우 공집합 제외
        cout<<cnt-1;
    } else{
        cout << cnt;
    }

}

 

바킹독-백트래킹 강의를 참고하였습니다.