Tricks

主要记录一些优化算法的小技巧。

折半搜索

一种优化搜索的技巧，往往可以把复杂度由O级别优化成。

例题:

平衡的子集

题意：给定个物品，每个物品有个权值，若一个子集可以被分成两个权值和相同的子集，就称该子集是平衡的，求有多少个平衡的子集。

考虑暴力搜索，相当于每个点有个系数，问整个序列权值和为的方案数，这样搜索是的，无法通过本题。我们可以先的爆搜出前一半能凑出的权值，拿存起来，然后爆搜后面一半，每次在里查找。特别注意一个子集的内部的划分是不算多次的，所以还要开个的数组去重。

总复杂度是。