Subset sum problem (Count)
(Mylib/Typical/subset_sum_count.cpp)
Operations
-
subset_sum_count(N, K, a[N])
Requirements
Notes
Problems
References
Code
#pragma once
#include <cassert>
#include <vector>
namespace haar_lib {
template <typename T>
auto subset_sum_count(int N, int K, const std::vector<int> &a) {
assert((int) a.size() == N);
std::vector<std::vector<T>> dp(2, std::vector<T>(K + 1));
dp[0][0] = 1;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= K; ++j) {
if (j >= a[i])
dp[(i + 1) & 1][j] = dp[i & 1][j - a[i]] + dp[i & 1][j];
else
dp[(i + 1) & 1][j] = dp[i & 1][j];
}
}
return dp[N & 1];
}
} // namespace haar_lib
#line 2 "Mylib/Typical/subset_sum_count.cpp"
#include <cassert>
#include <vector>
namespace haar_lib {
template <typename T>
auto subset_sum_count(int N, int K, const std::vector<int> &a) {
assert((int) a.size() == N);
std::vector<std::vector<T>> dp(2, std::vector<T>(K + 1));
dp[0][0] = 1;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= K; ++j) {
if (j >= a[i])
dp[(i + 1) & 1][j] = dp[i & 1][j - a[i]] + dp[i & 1][j];
else
dp[(i + 1) & 1][j] = dp[i & 1][j];
}
}
return dp[N & 1];
}
} // namespace haar_lib
Back to top page