Hacker Rank : Wet Shark and Two Subsequences

問題

https://www.hackerrank.com/challenges/wet-shark-and-two-subsequences
n項の数列{x_i}とrとsが与えられるので、
以下の条件を満たす数列の部分集合A,Bがいくつ存在するかを求める問題
・|A|=|B|
・sum(A)+sum(B)=r
・sum(A)-sum(B)=s

解法

sum(A)=(r+s)/2

sum(B)=(r-s)/2

となるのでdp[i][j][k]=i番目までの和がjとなるようなサイズkの部分列の個数

してdp.