给定子集 {1, 2, 3, .... N}。我必须找到从 1 到 N 的所有整数的集合可以分成两个总和相等的子集的方法数。
我脑子里什么都没有。我想尝试“暴力搜索”,但它可以限制时间。有什么快速算法吗?
最佳答案
对于从 1 到 n 的 k,它可以在多项式时间内计算为 (1 + x^k) 乘积中 x^(n(n+1)/4) 的系数。有几种方法可以评估产品;将各项相乘就足够了。
关于c++ - 集合 {1, 2, 3, ... N} 的划分,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28971124/