我想使用std::bitset在C++中实现binary counter。如果我为bitset明确开发一个加法函数，则算法的复杂度将高达O(n ^ 2)。有什么办法可以做到O(n)吗？
还对Horowitz和Sahni的子集和问题解决方案有很好的描述吗？除了维基百科，我找不到描述其算法的任何好资料。
最佳答案
对于第二个问题，“是否有关于Horowitz和Sahni的子集和问题解决方案的好描述？”，我发现了几篇文章:
Horowitz和Sahni的原始论文:
http://www.cise.ufl.edu/~sahni/papers/computingPartitions.pdf
关于Horowitz和Sahni的算法改进的Stackoverflow讨论:
Generate all subset sums within a range faster than O((k+N) * 2^(N/2))?
源代码:
http://www.diku.dk/hjemmesider/ansatte/pisinger/subsum.c