N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
주어지는 수열의 길이는 최대 40이다. 만약 40개의 부분수열을 모두 구한다면 가 되어 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)
따라서 입력받은 수열을 반으로 나눠 각자의 부분수열의 합을 먼저 구한다. () (백트래킹)
이때 계산된 두 부분수열의 합을 투포인터로 합치며 합친값이 S와 같은지 비교할 수도 있다.() 하지만 한 쪽 부분수열의 합을 구한 뒤, 나머지 부분수열의 합을 구할 때 그 합을 S에서 빼 해당 값이 한 쪽 부분수열의 합에 있는지 카운트하는 방법도 있다.() 아래 코드는 후자의 방식을 택해 나눈 오른쪽 수열의 합을 먼저 구하고, 왼쪽 수열의 합을 구하여 답을 구했다.
#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;
}
#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;
}