Template Function ADS::subsetSumDP

• Defined in File Pseudopolynomial.h

Function Documentation

template<class Bits = std::vector<bool>>
bool ADS::subsetSumDP(const std::vector<long> &A, long k, std::vector<std::vector<bool>> *rows = nullptr)

subsetSum(): M[ j ] tells whether some of A[ 0 .

. i ] sum to j; the vector M after each element goes to *rows, if given, the first one before any; O( n k ) time; M is a vector of Bits, std::vector< bool > by default, or boost::dynamic_bitset, or BitVector of ADS [see BitVector.h], with the same cells written

Pre:

k >= 0 and A is not negative

Post:

*rows, if given, has n + 1 rows