🔍 1208 부분수열의 합 2

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

---

🤔 풀이1 - map(sum, number of sum)

• 주어지는 수열의 길이는 최대 40이다. 만약 40개의 부분수열을 모두 구한다면 $2^{40}=10^{12}$ 가 되어 1초 이상의 시간이 걸릴 것이다.

• 만약 수열을 반으로 나누어 각각의 부분수열 합을 구한 뒤, 그 둘의 부분수열의 합을 구해도 전체 부분수열의 합을 구한 것과 똑같다.

  	eg) [-5 1 4 9] : 부분수열의 합 (-5, -4, -1, 0, 1, 4, 5, 9, 10, 13, 14)
  	------------------------------------------------------------------
  		[-5 1] : 부분수열의 합 (-5, -4, 0, 1)
  		[4 9] : 부분수열의 합 (0, 4, 9, 13)
  		=> (-5, -4, -1, 0, 1, 4, 5, 9, 10, 13, 14)

• 따라서 입력받은 수열을 반으로 나눠 각자의 부분수열의 합을 먼저 구한다. ($O(2^{n/2})$) (백트래킹)

• 이때 계산된 두 부분수열의 합을 투포인터로 합치며 합친값이 S와 같은지 비교할 수도 있다.($s1+s2=S\, ,O(2^{n/2})$) 하지만 한 쪽 부분수열의 합을 구한 뒤, 나머지 부분수열의 합을 구할 때 그 합을 S에서 빼 해당 값이 한 쪽 부분수열의 합에 있는지 카운트하는 방법도 있다.($S-s2=s1$) 아래 코드는 후자의 방식을 택해 나눈 오른쪽 수열의 합을 먼저 구하고, 왼쪽 수열의 합을 구하여 답을 구했다.

  • 부분수열의 합이 음수로 나올 수 있기 때문에 배열 인덱스로 값이 있는지 참조하는 방식보다 key-value쌍(합-몇 개가 있는지)의 map을 이용한다.
  • 다만 부분집합에는 공집합도 포함되기 때문에, S가 0일 경우에는 최종적으로 공집합인 경우를 (-1) 빼주어야 한다.

---

📝 코드1

#include <iostream>
#include <map>
using namespace std;

int arr[40];
int N, S;
long long ans = 0;
map<int, int> right_sum;

void subSumRight(int pivot, int sum) {
    if (pivot > N-1) {
        right_sum[sum]++;
        return ;
    }
    subSumRight(pivot+1, sum);
    subSumRight(pivot+1, sum+arr[pivot]);
}

void subSumLeft(int pivot, int sum) {
    if (pivot >= N/2) {
        ans += right_sum[S-sum];
        return ;
    }
    subSumLeft(pivot+1, sum);
    subSumLeft(pivot+1, sum+arr[pivot]);
}


int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    subSumRight(N/2, 0);
    subSumLeft(0, 0);

    if (S == 0) cout << ans-1;
    else cout << ans;

    return 0;
}

---

🤔 풀이2 - 이분 탐색

• 풀이1과 입력받은 수열을 반으로 나눠 각자의 부분수열의 합을 먼저 구하는 것은 까지는 같다. ($O(2^{n/2})$) (백트래킹)
• 다만 두 합을 더해 S가 되는 경우를 구하는 방법이 다르다. 여기서는 map 대신, S-합1 = 합2 를 만족하는 합2가 몇 개있는지 구하는 방식으로 진행한다.
• 먼저 둘로 나눈 수열에서 나올 수 있는 부분수열의 합을 각각 저장한 것이 합1, 합2 라고 하자. 우리는 조합(dfs)을 사용하여 합1, 합2 를 구한다.
• 그리고 S-[합1] = [합2] 를 만족하는 합2 가 몇개 있는지 구하기 위해서 이진 탐색을 사용할 것이다. 그러므로 합2가 모두 있는 배열을 정렬하고, lower_bound, upper_bound 를 이용하여 만족하는 합2의 개수를 정답에 더해주면 된다.

---

📝 코드2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> arr(40);

void comb(int idx, int sum, int bound, vector<int>* vec) {
    if (idx >= bound) {
        vec->push_back(sum);
        return ;
    }
    comb(idx+1, sum+arr[idx], bound, vec);
    comb(idx+1, sum, bound, vec);
}

int main() {
    int N, S;
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    vector<int> left;
    comb(0, 0, N/2, &left);
    
    vector<int> right;
    comb(N/2, 0, N, &right);
    sort(right.begin(), right.end());

    long long ans = 0;
    for (int i = 0; i < left.size(); i++) {
        int num = S - left[i];
        ans += ((upper_bound(right.begin(), right.end(), num) - lower_bound(right.begin(), right.end(), num)));
    }

    if (S == 0) cout << ans-1;
    else cout << ans;

    return 0;
}