写棋牌AI经常需要搜索所有非空真子集，举个例子

假设手牌{1,2,3,4}，那么我们可能需要搜索以下集合

                                                                   {1,2,3,4}

                                   {1}                  {2}                    {3}                    {4}                -----C

                   {1,2}   {1,3} {1,4}      {2,3} {2,4}             {3,4}                                       -----C

  {1,2,3}{1,2,4}   {1,3,4}            {2,3,4}                                                                      -----C

它有多少个子集呢？

这里根据高中数学，我们会发现每一行都是  n为集合元素个数，m为当前子集元素个数，即为从集合中挑出几个元素。根据二项式定理:C＋C＋C＋…＋C＝2ⁿ，我们可以得出所有子集个数为2ⁿ，又因为要减去空集和它自身，所以最终结果为2ⁿ-2。由于要遍历所有子集，所以我们的算法单从目前实现上来说最佳时间复杂度最优解为O（2ⁿ），因为遍历完这2ⁿ-2个子集中每一个，它的时间复杂度不可能低于这个，这里我们可以把这个子集抽象成一棵树去理解。

    怎么去实现它？最常想到的是DPS:

这里可以用递归实现该算法，递归通常需要一个结束条件来控制它的遍历深度，这里很显然，我们可以用层数来充当停止条件。第二个问题是，如何控制它的广度，我们清楚二叉树只有左右子树，但是非二叉树的子树难以确定，这里我们先将手牌排序，然后通过for循环和数组的size来控制它的广度。

这里说第一个技巧，删除数组元素通常不够方便，浪费时间，这里我们用swap将当前要删除的元素和最后一个元素交换，最后pop_back()即可，这里的时间复杂度为O（1）。

第二个技巧是map问题，减少map的使用，我们写这个算法时会用到hash原理，习惯于使用STL中的map容器，map容器的数据结构是红黑树，红黑树有左右指针和颜色。各占4个字节，我们可以采用size0f()来验证这个内存占用，在VS里加起来确实是12，顶多在加上键和值的大小，看起来似乎可以接受，实际上并非如此。因为map中的erase以及clear，不能马上释放内存。map有自己的机制回收内存，用erase以及clear之后，如果没有特殊需求，可以认为那部分内存已经释放了。map不会马上释放删掉内容的内存，而是会对内存进行预留，如果确实很长时间用不到预留的内存，才会释放。所以如果你想优化你的内存使用，减少使用map。

第三个技巧是使用map时，通过value查找key，这里可以使用find_if，使用方法，构造pred函数对象，这里关键是重载（）。如下是find_if代码

template <class InputIterator, class Predicate> 

InputIterator find_if(InputIterator first, InputIterator last,Predicate pred) 

{ 

while (first != last && !pred(*first)) ++first; 

return first; 

}

最后，说下优化，无法从算法实现上优化，我们可以优化这个策略，AI策略是加权求和，我们可以通过计算，推演出某些类型的打法必定是高于另一些的，采用贪心的局部最优

优化掉这些求解。这里不贴代码。