Let \(S=\sum_{i=1}^N P_i\). If \(S\) is odd, the answer is clearly \(0\). Hereafter assume \(S\) is even.

Let \(X\) be the number of subsets \(U\) of \(\{1 \dots N\}\) that satisfy \(\sum_{i\in U}P_i = \frac{S}{2}\).

Then, the answer is \(X^2-2X\).

Why \(X^2-2X\)

If we allow each team to be empty, there is a one-to-one correspondence between the \(X^2\) ways of independently choosing a pair of subsets \(U,V\) from \(X\) subsets and the following team formations:

• If \(i \in U\) and \(i \in V\), person \(i\) is in team \(A\)
• If \(i \notin U\) and \(i \notin V\), person \(i\) is in team \(B\)
• If \(i \in U\) and \(i \notin V\), person \(i\) is in team \(C\)
• If \(i \notin U\) and \(i \in V\), person \(i\) is in team \(D\)

Among these, empty teams arise only if \(U=V\) or \(U=\overline{V}\). (\(2X\) ways)

How to compute \(X\)

\(X\) can be computed in \(O(N (\sum{P_i}))\) by simple subset sum DP.

Side note

If we consider assigning a person with strength \(p\) to teams \(A,B,C,D\) as corresponding to vectors \((p,0),(-p,0),(0,p),(0,-p)\) respectively, the condition can be rephrased as the sum of vectors being \(\vec 0\).

Choosing one of these four vectors can be rephrased as independently choosing one from \((\frac{p}{2},\frac{p}{2}),(-\frac{p}{2},-\frac{p}{2})\) and one from \((\frac{p}{2},-\frac{p}{2}),(-\frac{p}{2},\frac{p}{2})\) and taking their sum, which yields a solution similar to the above.