子集和问题

【问题描述】给定一个整数的集合 S 和一个整数 X，问是否存在 S 的一个子集满足其中所有元素的和为 X。

【分析】子集和问题是一个NPC问题，与0/1背包问题并不相同。

这个问题有一个时间复杂度为O(2N/2)的较高效的搜索算法，其中 N 是集合 S 的大小。

第一步思想是二分。将集合 S 划分成两个子集 S1和 S2，它们的大小都是 N/2。对于 S1和 S2，分别枚举出它们所有的2N/2个子集和，保存到某种支持查找的数据结构中（如散列表）。然后就要将两部分结果合并，寻找是否有和为 X 的 S 的子集。

事实上，对于 S1的某个和为 X1的子集，只需寻找 S2是否有和为 X－X1的子集。假设采用的散列表是理想的，每次查找和插入都仅花费O(1)的时间。两步的时间复杂度显然都是O(2N/2)。

实践中，往往可以先将第一步得到的两组子集和分别排序，然后再用两个指针扫描的方法查找是否有满足要求的子集和。这样的实现，在可接受的时间内可以解决的最大规模约为 N=42。