这是一道标记为hard的题，确实比较hard
开始用了一个比较简单暴力的方法，其实也是DP思路，但是状态取的比较偷懒，直接用了所有的可能组合作为状态，虽然在求解过程中可以利用到已经搜索过的状态，但是整个搜索空间还是太大了，导致虽然结果正确，但是严重超时了：
class YetAnotherTwoTeamsProblem:
def count(self, skill):
ss = 0
for i in skill:
ss += i
#skill.sort()
mask = (1 << len(skill)) - 1
stat = {0:0}
sm = {0:100000}
su = {}
c = 0
for idx,s in enumerate(skill):
i = 1<<(idx+1)
for j in stat.keys():
n = i|j
if i == j or stat[j] < 0 or stat.get(n, 1) < 0:
continue
temp = s + stat[j]
sm[n] = min(sm[j], s)
h = su.get(temp, {}).get(sm[n], 0)
stat[n] = temp
if h != 0:
if h == -2:
c += 1
stat[mask^n] = -1
elif h == -1:
stat[mask^n] = -1
continue
d = ss - temp
if temp < d:
stat[n] = temp
elif temp == d:
stat[n] = -1
stat[mask^n] = -1
else:
if temp - d < sm[n]*2:
stat[n] = -2
stat[mask^n] = -1
c += 1
else:
stat[n] = -1
ht = su.get(temp, {})
if ht == {}:
su[temp] = {sm[n]:stat[n]}
else:
ht[sm[n]] = stat[n]
return c
又做了一次伸手党，看了解答后醒悟了，其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。
下面解释下我自己对该题的理解，不一定完全遵照我所看到的答案。我们大概可以想到，最后分组的结果，两个组各自的skill总和一定相差不多，都在全部队员总和sum/2附近。针对某一个队员，如果将他选入第一队，那么第一队的总和只要比第二队至少大1，那么这就是一个有效的解。所以在考察单个队员的时候，是不需要遍历整个空间（所有的可能总和构成）的，只需要从sum/2-skill[i]+1到sum/2（注意，这里sum/2因为是整型计算，可能等于总和的一半也有可能比一半的精确值少一点）。之所以是到sum/2，是因为总和不变，且i不在第一组就在第二组，我们这里考虑的是把i从第二组拿到第一组后，就能满足解的条件的那些可能状态。所以哪怕是第一组和为sum/2+1，就已经不满足这个可能状态了，因为此时如果将i给第一组，那么第一组一定大于第二组，但是将i从第一组拿到第二组，第一组的和回到sum/2+1，第二组还是比第一组小；如果到sum/2，那么至少还有一种可能，即skill[i]=2的情况。按照上面的总结：sum/2-skill[i]+1到sum/2为每个队员的考察搜索范围，那么最大的搜索范围是多少呢，一定是那个技能值最大的队员决定的，即sum/2-skill[greatest]+1到sum/2；这就大大减少了搜索空间。搜索的过程就是考察上述空间内所有的skill总和有哪些是可能的，把所有可能的和（作为dp状态的index）的组合数（dp状态数组的value）加到最终结果里面就可以了。
搜索从哪里开始呢，这一点非常重要，我们要让每趟搜索得出的信息都是正确的且都能对后面提供有利用价值的信息。不要忘了题目的要求，是要第一组中任意一个队员拿到第二组都要满足第二组总和大于第一组，这就是告诉我们如果我们当前考察的队员不是第一组最小的，那我们得到的结果将未必是有效解，所以要保证搜索正确必须按顺序从技能值最大队员开始搜索，于是每次考察的都是第一组最小的队员，如果他可以拿到第二组而仍然满足条件，那么全组都可以了。而且，每次只把当前队员纳入到搜索中，由于是按从大到小的顺序，前面所有积累的搜索结果对后面的搜索都是可以采纳的，因为当前技能值小于等于前面所有的值，对当前考察队员来说，记录下的都是有效组合。所以要从最牛的那个队员开始考察。
以组合的和为状态index，组合数为value的话，其转移方程就是，当前和j的组合数stat[j] += stat[j-skill[i]]；即考察某个队员i，他加入第一组之前的组技能总值有多少种组合（stat[index_old], index_old=j-skill[i]）方式，要加入其入组后达到的新状态index（新总合）的value中。计算状态value的过程，其实就是一个简化的背包问题，物品的大小是队员的skill值，包的容量是当前搜索的总和j，我们要求的不是背包物品的总价值，我们求的是j容量的背包被装满的可能组合数。每次搜索就是考察当前队员入队后（当前队里面所有人技能都大于等于他）和前面所有队员的所有种组合得到的和作为index，将它们统计到stat数组中。我们不用每次都从头开始搜索，只需把当前这个队员的skill在stat中滑动，按照状态转移方程传导之前的结果就更新了所有状态。
整个搜索过程就是，根据当前状态，考察剩余最大队员加入后构成解的可能和的组合数加入count，然后用新队员更新所有状态，为下一个队员考察做准备，此时该队员入队后对下一个考察的对象来说，所有的新的组合都是有效的。
我的实现代码：
class YetAnotherTwoTeamsProblem:
def count(self, skill):
ss = 0
for i in skill:
ss += i
sm = ss/2
skill.sort(reverse=True)
stat = {0:1}
c = 0
for i in skill:
for j in range(sm-i+1, sm+1):
# 已入选队员的和或者是0，或者>=当前队员skill
if (j == 0 or j >= i) and i+j > ss-i-j and j < ss-j:
c += stat.get(j, 0)
# 这里必须倒序，每次只跟前面已有的队员构成组合，自己不能和自己组队
for j in range(sm+i, i-1, -1):
stat[j] = stat.get(j, 0) + stat.get(j-i, 0)
return c